Information
- ID
- 97
- Time
- 2000ms
- Memory
- 256MiB
- Difficulty
- 7
- Tags
- # Submissions
- 61
- Accepted
- 15
- Uploaded By
这个题就是智力大冲浪的升级版,数据更大一些而已,我也就仅仅错了七八次而已(狗头保命)。 思路:比智力大冲浪多加了个dislike用来记录不能获得课程的截止日期的最大值,这样就可以更加快速判断是否能够完成这门课程的了
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7;
struct pre{
int term,credit;
}a[N];
bool s[N];//判断某一天是否被使用过了
int cmp(pre a,pre b){
return a.credit>b.credit;
}//学分高的放前面
inline int read() //快读,其实没必要
{
char c=getchar();
int x=0,f=1;
while(c<48 || c>57)
{
if(c=='-') f=-1;
c=getchar();
}
while(c>=48 && c<=57)
{
x=x*10+c-48;
c=getchar();
}
return x*f;
}
int main(){
int n;
n=read();
for(int i=0;i<n;i++){
a[i].term=read();
a[i].credit=read();
}
sort(a,a+n,cmp);
int sum=0,dislike=0;
for(int i=0;i<n;i++){
int flag=0;
if(a[i].term<=dislike) continue;//若低于dislike就不能够完成了,直接结束
for(int j=a[i].term;j>=1;j--){
if(!s[j]){
s[j]=1;
sum+=a[i].credit;
flag=1;
break;
}
}
if(!flag) dislike=max(dislike,a[i].term);//取截止日期的最大值
}
cout<<sum;
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.