Main » 2013 August 26 » [noip]工作安排 抓狂的乱搞
5:54 AM [noip]工作安排 抓狂的乱搞 |
O(nlogn)好不容易贪心+map+set+并查几乱搞累死我了 Prob.1748: [NOIP2011模拟赛_No.2]工作安排Time Limit: 1 Sec Memory Limit: 512 MBSubmit: 148 Solved: 38 [Submit][Status][Web Board] DescriptionFarmer John 有太多的工作要做啊！！！！！！！！为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。 他的工作日从0时刻开始，有1000000000个单位时间（！）。在任一时刻，他都可以选择编号1~N的N(1 <= N <= 100000)项工作中的任意一项工作来完成。 因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有N个工作，虽然还是有可能。 对于第i个工作，有一个截止时间D_i(1 <= D_i <= 1000000000)，如果他可以完成这个工作，那么他可以获利P_i( 1<=P_i<=1000000000 ). 在给定的工作利润和截止时间下，FJ能够获得的利润最大为多少呢？答案可能会超过32位整型。 Input第1行：一个整数N. Output输出一行，里面有一个整数，表示最大获利值。 Sample Input3
2 10
1 5
1 7
Sample Output17 HINT输出说明： 第1个单位时间完成第3个工作(1,7)，然后在第2个单位时间完成第1个工作(2,10)以达到最大利润 Sourcecode#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<map> #include<set> #define ittype set<int>::iterator #define N 500010 using namespace std; map<int,int> hash; set<int> pos; int f[N],m[N]; int cnt=0,n; struct node { long long D,P; }; node a[N]; int cmp(node a,node b) { if (a.P>b.P) return 1; if (a.P<b.P) return 0; if (a.P==b.P) { if (a.D>b.D) return 1; return 0; } } int min(int a,int b) { if (a<b) return a; return b; } int getf(int x) { if (f[x]!=x) f[x]=getf(f[x]); return f[x]; } void merge(int p1,int p2) { int f1=getf(p1); int f2=getf(p2); int m1=m[f1]; int m2=m[f2]; f[f1]=f2; m[f2]=min(m1,m2); } void Ins(int p) { cnt++; f[cnt]=cnt; m[cnt]=p; hash[p]=cnt; pos.insert(p); ittype it1,it2; it2=it1=pos.find(p); it1--;it2++; if (it1!=pos.begin()) if (*it1==(p-1)) { int x1=hash[*it1]; int x2=cnt; merge(x1,x2); } if (it2!=pos.end()) if (*it2==(p+1)) { int x1=hash[*it2]; int x2=cnt; merge(x1,x2); } } int findpos(int p) { if (pos.find(p)==pos.end()) { Ins(p); return p; }else { int x=getf(hash[p]); int res=m[x]; res--; if (res>0) Ins(res); return res; } } int main() { scanf("%d",&n); int i; for (i=1;i<=n;i++) scanf("%d %d",&a[i].D,&a[i].P); sort(a+1,a+1+n,cmp); long long ans=0; pos.insert(0); for (i=1;i<=n;i++) { int p=a[i].D; int new_p=findpos(p); if (new_p>0) ans+=a[i].P; } printf("%lld\n",ans); } |
|
|
| Total comments: 0 | |