admin 管理员组

文章数量: 1086019

[截止时间 贪心算法]某学科老师布置了n个题目，每个题目都有相应的分数及截止日期。各个题目的分数及截止日期可能并不相同。对某题目而言，如果在该题目的截止日期前完成则可获得对应的分数，否则无法得分。

 

对该实例而言，得分最大的作业完成方案为花费4天时间依次完成题目2,6,3,7。得分为15。

【输入形式】 

输入数据第一行为一个整数n (0 <= n <= 10000), 表示题目数目
之后n行各有两个整数, 第i行为 pi, di (1 <= pi, di <= 10000)，分别表示第i个题目的分数和截止时间

【输出形式】

【样例输入】

4 
50 2 
10 1 
20 2 
30 1

【样例输出】

80

C++代码实现如下：

 #include<iostream>#include<algorithm>#include<cstring>using namespace std;struct node{long p,d;bool operator < (const node& a)const{return p>a.p;}};long n;node a[10000];long  vis [10000];int main(){cin>>n;for(long i=0;i<n;i++){cin>>a[i].p>>a[i].d;}sort(a,a+n);memset(vis,0,sizeof(vis));long sum=0;for(long i=0;i<n;i++){for(long j=a[i].d;j>=1;j--){if(!vis[j]){vis[j]=1;sum+=a[i].p;break;}}}cout<<sum<<endl;}

本文标签： 截止时间 贪心算法某学科老师布置了n个题目，每个题目都有相应的分数及截止日期各个题目的分数及截止日期可能并不相同对某题目而言，如果在该题目的截止日期前完成则可获得对应的分数，否则无法得分

版权声明：本文标题：[截止时间 贪心算法]某学科老师布置了n个题目，每个题目都有相应的分数及截止日期。各个题目的分数及截止日期可能并不相同。对某题目而言，如果在该题目的截止日期前完成则可获得对应的分数，否则无法得分。 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1700382338a422818.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。