首页 > 代码库 > HDU_4864 Task 贪心
HDU_4864 Task 贪心
今天多校的一道题，哎，多校被中学生碾压了
发现自己很怕敲贪心，这道题其实贪心特性相当明显，我看这个题算比较早，还在想各种递推或者dp那种
后来还是聪哥马上反应过来了
首先，对于任何的task，因为最后的money是 500*x+2*y,所以，在得到最多money方面，肯定是x的优先级高，x相同的时候再比较y
然后题目是要求 在保证最多任务完成量的前提下，money最多，在任务完成量方面，首先，题目一个很明显的说法是一个机器只能跟一个task对应，所以，一个task如果只是占用了刚好够自己用的机器，那绝对就是最优的，因为就算替换他，也就是1换1，没有任何区别，当然，如果他占用了比自己好很多的机器就可能有问题了，因为可能有更高级的任务会被排开，这样原本可能可以完成2件 就只能完成1件，所以，我们只要保证这个task是刚好满足这个机器，即可
于是，我们把task按照money最大的原则降序排序，把他们依次放到最适合他们的机器上（机器照同样的规则排完序，然后二分即可）。如果能放就放，不能放就扔了。根据上面的分析，这样求出来的结果必然是最优的。。而且在存在多种可能的情况下，因为我是按最大价值放的，得到的money也必定是最优的
在处理方面还有点小技巧，我一开始把所有机器全部存在一个vector里面，然后排序 一个个二分，满足条件的 在vector里面erase这个值，结果TLE了
首先要说一下 vector是线性结构，他的erase是擦除当前数，然后把后面的值一个个往前移，复杂度其实有点高，平均下来为On,如果用set就好多了，不仅自动排序，erase也是logN的。
还有题目有个隐含条件就是y最多只有100，那我完全可以开个V[110]，分开存贮机器，然后在可能的区间里面再二分。。这样就快多了，最后也证明是这样过
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#define LL __int64using namespace std;struct node{ int x,y;}tasks[100010];bool cmp(node a,node b){ if (a.x==b.x) return a.y<b.y; return a.x<b.x;}int n,m;vector<int> v[110];int bs(int p,int q){ int L=0,R=v[p].size(),mid; while (L<R) { mid=(L+R)>>1; if (v[p][mid]<tasks[q].x) L=mid+1; else R=mid; } return L;}int main(){ int a,b; while (scanf("%d%d",&m,&n)!=EOF) { int maxn=0; for (int i=0;i<110;i++) v[i].clear(); for (int i=1;i<=m;i++){ scanf("%d%d",&a,&b); v[b].push_back(a); maxn=max(b,maxn); } for (int i=1;i<=n;i++){ scanf("%d%d",&a,&b); tasks[i].x=a; tasks[i].y=b; } sort(tasks+1,tasks+1+n,cmp); for (int i=0;i<=maxn;i++) sort(v[i].begin(),v[i].end()); LL ans=0; int sum=0; for (int i=n;i>=1;i--){ for (int j=tasks[i].y;j<=maxn;j++){ int loc=bs(j,i); if (loc>=v[j].size()) continue; else{ v[j].erase(v[j].begin()+loc); ans+=(LL)tasks[i].x*500+(LL)tasks[i].y*2; sum++; break; } } } printf("%d %I64d\n",sum,ans); } return 0;}