首页 > 代码库 > hdu 4864

hdu 4864

2024-07-13 15:14:01   217人阅读

基本思想是贪心。

对于价值c=500*xi+2*yi，yi最大影响100*2<500,所以就是求xi总和最大。可以先对机器和任务的时间从大到小排序。从最大时间的任务开始，找出满足任务时间要求的所有机器，从中找出等级最低且满足任务等级要求的机器匹配。依次对任务寻找满足要求的机器。

主要是对stl不熟悉啊，自己的想法

 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 map<int, int> p;19 map<int, int>::iterator it;20 struct s{21     int xi, yi;22     bool operator < ( const s & b ) const{23         return xi > b.xi || ( xi == b.xi && yi > b.yi);24     }25 }a[mnx], b[mnx];26 int main(){27     int n, m;28     while( scanf( "%d%d", &n, &m ) != EOF ){29         p.clear();30         for( int i = 0; i < n; i++ ){31             scanf( "%d%d", &a[i].xi, &a[i].yi );32         }33         for( int i = 0; i < m; i++ ){34             scanf( "%d%d", &b[i].xi, &b[i].yi );35         }36         sort( a, a+n );37         sort( b, b+m );38         int j = 0, ans1 = 0; ll ans2 = 0;39         for( int i = 0; i < m; i++ ){40             while( j < n && a[j].xi >= b[i].xi ){41                 p[a[j].yi]++;42                 j++;43             }44             it = p.lower_bound( b[i].yi );45             if( it != p.end() ){46                 ans1++;47                 ans2 += b[i].xi * 500 + b[i].yi * 2;48                 int t = it->first;49                 p[t]--;50                 if( p[t] == 0 ){51                     p.erase( t );52                 }53             }54         }55         printf( "%d %I64d\n", ans1, ans2 );56     }57     return 0;58 }

 

也不是很对，没ac出来


联系
我们