传送门
代码1
点击查看代码
#include<bits/stdc++.h>
using namespace std;struct game{//结构体用来存放每个游戏的时间和利益 int t;int r;
}a[505];bool cmp(game a,game b){//cmp函数（结构体排序规则） return a.r>b.r;
}
bool vis[505];//用来标记该时间是否空闲
int sum;//收益和
int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i].t);}for(int i=1;i<=n;i++){scanf("%d",&a[i].r);}sort(a+1,a+n+1,cmp);//排序 for(int i=1;i<=n;i++){bool k=0;//用来记录该任务是否能按时完成 for(int j=a[i].t;j>=1;j--){//按时间从大到小去枚举 if(vis[j]==0){//说明有时间 vis[j]=1;//标记，说明该时间已被占用 k=1;//该任务可以完成 break;}}if(k==1){//若该任务可以完成 sum+=a[i].r;//将该任务的收益加入累加器 }}printf("%d",sum);//输出 return 0;
}
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int n, ans;
// 使用小顶堆来维护当前选择的任务奖励
priority_queue <int, vector<int>, greater<int> > q;struct node {int t; // 任务的截止时间int r; // 任务的奖励
} p[505];// 比较函数：按截止时间从小到大排序
bool cmp(node a, node b) {return a.t <= b.t;
}int main() {scanf("%d", &n);// 读取每个任务的截止时间for(int i = 1; i <= n; i++) scanf("%d", &p[i].t);// 读取每个任务的奖励for(int i = 1; i <= n; i++) scanf("%d", &p[i].r);// 按截止时间从小到大排序sort(p + 1, p + 1 + n, cmp);// 贪心算法核心部分for(int i = 1; i <= n; i++) {// 将当前任务的奖励加入堆中q.push(p[i].r);// 关键：如果当前时间点已经超过了堆中任务的数量// 说明无法在截止时间内完成所有已选择的任务// 因此需要移除奖励最小的任务if(p[i].t < q.size()) {q.pop();}}// 计算最终选择的所有任务的奖励总和while(q.size()) {ans += q.top(); q.pop();}printf("%d", ans);return 0;
}