原题 传送门
【题目描述】
老师在开学第一天就把所有作业都布置了,每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为10,要求在6天内交,那么要想拿到这10学分,就必须在第6天结束前交。
每个作业的完成时间都是只有一天。例如,假设有7次作业的学分和完成时间如下:
作业号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
期限 | 1 | 1 | 3 | 3 | 2 | 2 | 6 |
学分 | 6 | 7 | 2 | 1 | 4 | 5 | 1 |
最多可以获得15学分,其中一个完成作业的次序为2,6,3,1,7,5,4,注意可能d还有其他方法。
你的任务就是找到一个完成作业的顺序获得最大学分。
【输入】
第一行一个整数N,表示作业的数量。
接下来N行,每行包括两个整数,第一个整数表示作业的完成期限,第二个数表示该作业的学分。
【输出】
输出一个整数表示可以获得的最大学分。保证答案不超过longint范围。
【输入样例】
7 1 6 1 7 3 2 3 1 2 4 2 5 6 1
【输出样例】
15
第一眼看这个题,和智力大冲浪有点像,甚至还比那个题简单些,不用判断做不完怎么办。
贪心策略:
为了使学分尽可能的多,我们要尽可能得做学分多的作业,我们先按照学分从大到小排序,然后枚举每一个作业,尽量让这个作业贴着期限完成;
我们可以从某一个作业的期限往前找,若找到没安排作业的时间点就将它安排上。
代码如下:
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct homework { int k,date; }a[1000001]; int read() { char ch=getchar(); int a=0,x=1; while(ch<'0'||ch>'9') { if(ch=='-') x=-x; ch=getchar(); } while(ch>='0'&&ch<='9') { a=(a<<3)+(a<<1)+(ch-'0'); ch=getchar(); } return a*x; } int cmp(homework x,homework y) { return x.k>y.k; //按照学分从大到小排序 } int n,sum,hash[1000001]; int main() { n=read(); for(int i=1;i<=n;i++) { a[i].date=read(); a[i].k=read(); } sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) { int bj=1; for(int j=a[i].date;j>=1;j--) //尽量让作业贴着期限做,来减少对其他作业的影响 { if(hash[j]==0) { hash[j]=1; bj=0; sum+=a[i].k; break; } } } cout<<sum<<endl; return 0; }
但是将这份代码交上去后我们发现有两个点TLE了!我们要进一步优化!
如果我们对某一个作业 i 进行安排,发现从a[i].date枚举到1它们的hash都为1,也就是说:从1~a[i].date都已经安排满了,安排不了其他的作业了;
我们可以用q来记录这个a[i].date,对于后面的作业,如果它的期限a[i+1].date<=q,说明这个作业一定安排不了,我们直接跳出就好了,不用再枚举了;
AC代码如下:
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct homework { int k,date; }a[1000001]; int read() { char ch=getchar(); int a=0,x=1; while(ch<'0'||ch>'9') { if(ch=='-') x=-x; ch=getchar(); } while(ch>='0'&&ch<='9') { a=(a<<3)+(a<<1)+(ch-'0'); ch=getchar(); } return a*x; } int cmp(homework x,homework y) //按照学分从大到小排序 { return x.k>y.k; } int n,sum,q,hash[1000001]; int pan(int x) { for(int i=a[x].date;i>=1;i--) { if(hash[i]==0) { hash[i]=1; return 1; } } q=a[x].date; //如果到了这里,说明1~a[x].date已经安排满了,用q记录下来 return 0; } int main() { n=read(); for(int i=1;i<=n;i++) { a[i].date=read(); a[i].k=read(); } sort(a+1,a+1+n,cmp); for(int i=1;i<=n;i++) { if(a[i].date<q) continue; //直接跳出,节省时间 if(pan(i)) sum+=a[i].k; } printf("%d ",sum); return 0; }