1、要能够分析出贪心的理由
2、在lv里面进行lower_bound : 因为对于task的time本来就已经是从大到小排好序的，对于task里的每个time我们应该从最小的level开始放，
因为可能在task后面有比较大的lv;
3、lower_bound的用法
4、二分的写法
5、比较函数cmp
#include #include #include #include #include #include #include #include #include #include using namespace std; #define clr(x) memset(x,0,sizeof(x)) #define fp1 freopen("in.txt","r",stdin) #define fp2 freopen("out.txt","w",stdout) #define pb push_back #define INF 0x3c3c3c3c typedef __int64 LL; const int maxn = 1e5+100; typedef struct nn{ LL time, lv; }nn; nn task[maxn], mac[maxn]; int N, M; multiset ss[150]; bool cmp(nn a, nn b){ if(a.time>b.time) return true; else { if(a.time==b.time) return a.lv > b.lv; else return false; } return false; } int main() { //fp1; while(scanf("%d %d", &N, &M) == 2){ for(int i = 0;i < 150;i++) ss[i].clear(); for(int i = 1;i <= N;i++){ scanf("%I64d %I64d", &mac[i].time, &mac[i].lv); ss[mac[i].lv].insert(mac[i].time); } for(int i = 1;i <= M;i++){ scanf("%I64d %I64d", &task[i].time, &task[i].lv); } sort(task+1, task+1+M, cmp); LL count = 0, sum = 0; for(int i = 1;i <= M;i++){ for(int j = task[i].lv;j < 150;j++){ if(ss[j].size() == 0) continue; if(ss[j].lower_bound(task[i].time) == ss[j].end()) { continue; } else{ count ++; multiset ::iterator it = ss[j].lower_bound(task[i].time); sum += (task[i].time*500 + task[i].lv*2); ss[j].erase(it); break; } } } printf("%I64d %I64d\n", count, sum); } return 0; }