首页 > 代码库 > hdu 4864(2) 线段树

hdu 4864(2) 线段树

2024-07-13 15:32:55   225人阅读

对task和machine的yi由小到大进行排序，然后对machine来跟task配对。当machine[].yi >= task[].yi时，就更新线段树，在1-1440上做线段树,线段树存的是task[].xi，同时用用优先队列保存task[].yi；当machine[].yi < task[].yi时，就查找 1到machine[].xi最大的值。如果存在最大值的话，把优先队列里的task[].yi取出来。。这样一个machine就匹配到了一个最优的任务。还是看代码好好意会吧，细节挺多的

 1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #include<string> 6 #include<queue> 7 #include<cmath> 8 #include<map> 9 10 using namespace std;11 12 #define mnx 10005013 #define ll long long14 #define inf 0x3f3f3f3f15 #define lson l, m, rt << 116 #define rson m+1, r, rt << 1 | 117 18 priority_queue<int> q[1500];19 int cnt[1500], sum[8000];20 struct s{21     int xi, yi;22     bool operator < ( const s & b ) const{23         return yi < b.yi;24     }25 }a[mnx], b[mnx];26 void pushup( int rt ){27     sum[rt] = max( sum[rt<<1], sum[rt<<1|1] );28 }29 void build( int l, int r, int rt ){30     if( l == r ){31         sum[rt] = -1;32         return ;33     }34     int m = ( l + r ) >> 1;35     build( lson ), build( rson );36     pushup( rt );37 }38 int find( int L, int R, int l, int r, int rt ){39     if( L <= l && R >= r ){40         return sum[rt];41     }42     int m = ( l + r ) >> 1;43     int ret = -1;44     if( L <= m ) ret = max( ret, find( L, R, lson ) );45     if( R > m ) ret = max( ret, find( L, R, rson ) );46     return ret;47     48 }49 void update( int u, int v, int l, int r, int rt ){50     if( l == r ){51         sum[rt] = v;52         return ;53     }54     int m = ( l + r ) >> 1;55     if( u <= m ) update( u, v, lson );56     else update( u, v, rson );57     pushup( rt );58 }59 int main(){60     int n, m;61     const int nn = 1450;62     while( scanf( "%d%d", &n, &m ) != EOF ){63         for( int i = 0; i < nn; i++ ){64             while( !q[i].empty() ) q[i].pop();65         }66         memset( cnt, 0, sizeof(cnt) );67         for( int i = 0; i < n; i++ ){68             scanf( "%d%d", &a[i].xi, &a[i].yi );69         }70         for( int i = 0; i < m; i++ ){71             scanf( "%d%d", &b[i].xi, &b[i].yi );72         }73         sort( a, a+n );74         sort( b, b+m );75         build( 1, nn, 1 );76         int j = 0, ans1 = 0; ll ans2 = 0;77         for( int i = 0; i < n; i++ ){78             while( j < m && a[i].yi >= b[j].yi ){79                 if( !cnt[b[j].xi] ){80                     update( b[j].xi, b[j].xi, 1, nn, 1 );81                 }82                 cnt[b[j].xi]++;83                 q[b[j].xi].push( b[j].yi );84                 j++;85             }86             int t = find( 1, a[i].xi, 1, nn, 1 );87             if( t == - 1 ) continue;88             cnt[t]--;89             if( cnt[t] == 0 ) update( t, -1, 1, nn, 1 );90             int tt = q[t].top();  q[t].pop();91             ans1++;92             ans2 += t * 500 + tt * 2;93         }94         printf( "%d %I64d\n", ans1, ans2 );95     }96     return 0;97 }


联系
我们