nazgul's Blog

pku 1201 Intervals

 

题目意思：给一些整数区间[x,y]，要求找一个元素个数最小的集合s，使得每个区间在集合s中都有z个元素。
 
分析一：贪心，将区间[x,y]按照从大到小排列，取尽可能前面的z个元素。结果悲剧TLE。
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <stdlib.h>
 
#define MAXN 50001
 
struct node
{
    int x, y, z;
}ivl[MAXN];
int n, ql, l;
int q[MAXN], temp[MAXN], f[MAXN] = {0};
 
int cmp( const void *a, const void *b )
{
    return ( ( struct node * )b )->x - ( ( struct node * )a )->x;
}
 
int main()
{
    int c, i, j, t, ty;
    scanf( "%d", &n );
    for ( i = 0; i < n; ++i )
        scanf( "%d%d%d", &ivl[i].x, &ivl[i].y, &ivl[i].z );
    qsort( ivl, n, sizeof( ivl[0] ), cmp );
    for ( ql = i = 0; i < n; ++i )
    {
        t = ivl[i].z; ty = ivl[i].y;
        for ( c = 0, j = ql-1; j >= 0 && c < t; --j )
            if ( ty >= q[j] )
                c++;
        l = 0;
        for ( j = ivl[i].x; c < t; ++j )
            if ( !f[j] )
            {
                temp[l++] = j;
                f[j] = 1; ++c;
            }
        for ( j = l-1; j >= 0; --j )
            q[ql++] = temp[j];
    }
    printf( "%d\n", ql );
    return 0;
}

分析二：差分约束系统，对于整数i,用a[i]表示i以前有多少个在集合s中，则对于区间[x,y]有a[y]-a[x]>=z，即a[x]-a[y]<=-z，在图中表示从y到x有一条权值为-z的边。另外结果还要满足a[i+1]-a[i]<=1,a[i]-a[i+1]<=0。分别表示从i到i+1有一条权为1的边和i+1到i有一条权为0的边。204ms A了

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <string.h>
#define MAXN 50101
 
struct node
{
    int v, d, next; //
}pot[160000];
int g[MAXN], pl;
int dis[MAXN], visit[MAXN], queue[MAXN], used[MAXN];
 
int spfa( int n, int s ) //点的个数，源点，汇点
{
    int top, tail, u, v, k;
    memset( dis, 0x7f, sizeof( dis ) );
    memset( visit, 0, sizeof( visit ) );
    dis[s] = 0; top = 0; tail = 1;
    queue[0] = s; visit[s] = 1;
    while ( top != tail ) //循环队列
    {
        u = queue[top]; visit[u] = 0;
        top++;
        if ( top == n ) top = 0;
        for ( k = g[u]; k != -1; k = pot[k].next )
        {
            v = pot[k].v;
            if ( dis[v] - pot[k].d > dis[u] )
            {
                dis[v] = dis[u] + pot[k].d;
                if ( !visit[v] )
                {
                    queue[tail] = v; visit[v] = 1;
                    tail++;
                    if ( tail == n ) tail = 0;
                }
            }
        }
    }
    return dis[n-1] - dis[s];
}
 
void addEdge( int u, int v, int w )
{
    pot[pl].next = g[u];
    g[u] = pl;
    pot[pl].v = v; pot[pl].d = w;
    pl++;
}
 
int main()
{
    int u, v, w, n, m = 0, mi = 0x7fffffff;
    memset( g, -1, sizeof( g ) );
    memset( used, 0, sizeof( used ) );
    pl = 0;
    scanf( "%d", &n );
    while ( n-- )
    {
        scanf( "%d%d%d", &u, &v, &w );
        v++;
        addEdge( u, v, -w );
        if ( v > m ) m = v;
        if ( u < mi ) mi = u;
    }
    for ( u = mi; u <= m; ++u )
    {
        addEdge( u, u+1, 0 );
        addEdge( u+1, u, 1 );
    }
    printf( "%d\n", -spfa( m+1, mi ) );
    return 0;
}

本来以为用离散化可以速度更快的，结果更慢了。。。。时间：329ms

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 50101
 
struct node
{
    int v, d, next; //
}pot[160000];
struct _Queue
{
    int value, label;
}q[MAXN];
int hs[MAXN], queue[MAXN], g[MAXN], l, pl; //hash, queue, length of queue
int dis[MAXN], visit[MAXN];
 
int cmp( const void *a, const void *b )
{
    return ( ( struct _Queue * )b )->value - ( ( struct _Queue * )a )->value;
}
 
void spfa( int n, int s ) //点的个数，源点，汇点
{
    int top, tail, u, v, k;
    memset( dis, 0x7f, sizeof( dis ) );
    memset( visit, 0, sizeof( visit ) );
    dis[s] = 0; top = 0; tail = 1;
    queue[0] = s; visit[s] = 1;
    while ( top != tail ) //循环队列
    {
        u = queue[top]; visit[u] = 0;
        top++;
        if ( top == n ) top = 0;
        for ( k = g[u]; k != -1; k = pot[k].next )
        {
            v = pot[k].v;
            if ( dis[v] - pot[k].d > dis[u] )
            {
                dis[v] = dis[u] + pot[k].d;
                if ( !visit[v] )
                {
                    queue[tail] = v; visit[v] = 1;
                    tail++;
                    if ( tail == n ) tail = 0;
                }
            }
        }
    }
}
 
void addEdge( int u, int v, int w )
{
    pot[pl].next = g[u];
    g[u] = pl;
    pot[pl].v = v; pot[pl].d = w;
    pl++;
}
 
int HashKy( int u )
{
    if ( hs[u] != -1 ) return hs[u];
    q[l].value = u; q[l].label = l;
    hs[u] = l; l++;
    return l-1;
}
 
void hashAddEdge( int u, int v, int w )
{
    addEdge( HashKy( u ), HashKy( v ), w );
}
 
int main()
{
    int u, v, w, n;
    memset( hs, 0, sizeof( hs ) );
    memset( g, -1, sizeof( g ) );
    memset( hs, -1, sizeof( hs ) );
    pl = l = 0;
    scanf( "%d", &n );
    while ( n-- )
    {
        scanf( "%d%d%d", &u, &v, &w );
        hashAddEdge( v+1, u, -w );
    }
    qsort( q, l, sizeof( q[0] ), cmp );
    for ( u = 0; u < l-1; ++u )
    {
        addEdge( q[u].label, q[u+1].label, 0 );
        addEdge( q[u+1].label, q[u].label, q[u].value-q[u+1].value );
    }
    spfa( l, q[0].label );
    printf( "%d\n", dis[q[0].label]-dis[q[l-1].label] );
    return 0;
}

 

POJ 差分约束系统 Comments(0) 2010年10月20日 21:37




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee