6 solutions
-
2
题目解析：
根据题意可知，本题要求挣的钱最多即所有的项目能完成就完成，是在存在时间冲突的就舍弃惩罚金额最小的项目，使舍弃的所有项目的惩罚金额最小。所以每个项目的惩罚金额就是其价值，我们的目标就是要使价值最大。自然而然的，我们就会想到贪心，其实本题有两种贪心算法，我就分享我使用的，首先用结构体储存项目的时间和价值，根据价值由大到小的排序，优先选择价值最大的项目完成，每个项目的时限是k，可以在1~k时间内完成项目且收获的价值是一样的，优先选择在最后时限k完成项目，以求不浪费时间，如果最后时限k已经被占用就安排在k-1，以此为准则进行安排即一定是最优解。
参考代码：
#include <bits/stdc++.h> using namespace std; typedef struct { int t; int v; }player; bool cmp(player a, player b) { return a.v > b.v; } int main() { int m,sum = 0,n, t = 1,ans = 0; int x[600]; memset(x,0,sizeof(x)); cin >> m >> n; player arr[600]; int min = 1; for(int i = 1; i <= n; i++) { cin >> arr[i].t; } for(int i = 1; i <= n; i++) { cin >> arr[i].v; ans += arr[i].v; } sort(arr + 1, arr + n + 1,cmp); for(int i = 1; i <= n; i++) { if(x[arr[i].t] == 0) { x[arr[i].t] = 1; sum += arr[i].v; } else { int temp = arr[i].t; while(x[temp] == 1 && temp >= 1) { temp--; } if(temp >= 1) { x[temp] = 1; sum += arr[i].v; } } } cout << m + sum - ans; return 0; } -
1
// 思想： 先按时间升序 (金钱的顺序可升序可降序) // 再用 变量time 记录当前的时间，若没有项目有时间冲突，则全部游戏都可以顺利完成（废话） // 否则，从 i = 1 到 当前位置 枚举，看是否存在一个 项目金钱 比此项目金钱少 （可以用优先队列或小根堆优化） // 若存在，则选择放弃完成那个项目，再用st[N数组标记那个项目已经放弃（小根堆或优先队列则直接出队） // 若不存在，则放弃当前项目是最优选择 // 最后 m - res(放弃项目的金钱) 则是答案 #include<iostream> #include<algorithm> #include <vector> #include <queue> using namespace std; #define int long long #define x first #define y second typedef pair<int,int> PII; const int N = 550; vector<PII> v(N); int b[N], c[N]; bool st[N]; bool cmp(PII &a, PII &b) { if( a.x != b.x ) return a.x < b.x; return a.y > b.y; } signed main() { int m, n, res = 0; cin >> m >> n; for(int i = 1; i <= n; i ++ ) cin >> v[i].x; for(int i = 1; i <= n; i ++ ) cin >> v[i].y; //sort(v.begin()+1, v.begin()+1+n); sort(v.begin()+1, v.begin()+1+n, cmp); int time = 1; for(int i = 1; i <= n; i ++ ) { if( time > v[i].x ) { int idx = i; for(int j = 1; j < i; j ++ ) if( v[j].y < v[idx].y && !st[j] ) idx = j; st[idx] = true; res += v[idx].y; } else time ++; } cout << m - res; }
//小根堆版本 #include<iostream> #include<algorithm> #include <vector> #include <queue> using namespace std; #define int long long #define x first #define y second typedef pair<int,int> PII; const int N = 550; vector<PII> v(N); int b[N], c[N]; priority_queue<int,vector<int>,greater<int> >q; bool cmp(PII &a, PII &b) { if( a.x != b.x ) return a.x < b.x; return a.y > b.y; } signed main() { int m, n, res = 0; cin >> m >> n; for(int i = 1; i <= n; i ++ ) cin >> v[i].x; for(int i = 1; i <= n; i ++ ) cin >> v[i].y; //sort(v.begin()+1, v.begin()+1+n); sort(v.begin()+1, v.begin()+1+n, cmp); int time = 1; for(int i = 1; i <= n; i ++ ) { if( time > v[i].x ) { if( q.top() < v[i].y ) { res += q.top(); q.pop(); q.push(v[i].y); } else res += v[i].y; } else time ++, q.push(v[i].y); } cout << m - res; } -
1
题意分析：
不知道有没有小伙伴和我一样，没有第一时间读懂题
这里有一句非常关键的句子"比赛时间分成n个时段~~~~~~每个时间必须在规定时限t前完成。"深入理解到他的意思，我们就可以用一个bool数组来实现了
注意：
为了更多的钱，将扣钱多的先安排，且从边界倒序遍历。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> typedef long long ll; using namespace std; bool vis[505]; struct node{ int e,b; }a[1003]; int cmp(node x,node y) { if(x.e==y.e) return x.b>y.b; return x.e > y.e; } int main() { ll m,n; scanf("%lld%lld",&m,&n); for(int i = 1;i <= n;i++) { scanf("%d",&a[i].b); } for(int i = 1;i <= n;i++) { scanf("%d",&a[i].e); } sort(a + 1,a + n + 1,cmp); for(int i=1;i<=n;i++) { if(!vis[a[i].b]) { vis[a[i].b]=true; } else { int j; for(j=a[i].b-1;j>0;j--) { if(!vis[j]) { vis[j]=true; break; } } if(j==0) { m-=a[i].e; } } } printf("%lld\n",m); return 0; } -
0
#include<stdio.h> //最开始把这道题理解错了，题目说的是比赛总共n个时段，每个游戏都要在 //ti的时段之前完成，最开始当成时间去了，我说每个都一个小时内完成不刚好就可以全部完成吗 //就没有排序的意义了，但是时段不一样，这个时段被占用了就不能再使用了 //想要被扣的钱最少，很明显的贪心算法，让最贵的排在最前先去完成 typedef struct activity{ int t;//游戏的完成期限 int cost;//游戏的完成时间 }act; act array[600]; int book[600]; int main(){ int m,n; act temp; int flag; int x; scanf("%d",&m);//一开始奖励给参赛者的钱 scanf("%d",&n);//n个小游戏也就是n个时段 for(int i=0; i<n; i++){ scanf("%d",&array[i].t);//每个游戏规定的时段 } for(int i=0; i<n; i++){ scanf("%d",&array[i].cost);//每个游戏对应的花费 } for(int i=0; i<n-1; i++){ for(int j=0; j<n-i-1; j++){ if(array[j+1].cost>array[j].cost){ temp = array[j+1]; array[j+1] = array[j]; array[j] = temp; } } } for(int i=0; i<n; i++){ if(!book[array[i].t])//如果这个时段没有被占用则直接使用 { book[array[i].t] = 1;//将这个时段标记为1 } else{//如果这个时段已经被占用则选取这个时段以内的 x = array[i].t;//4 x--;//3 while(book[x] == 1 && x>=1 ){ x--; } if(x){ book[x] = 1; } else{ m-=array[i].cost; } } } printf("%d\n",m); } -
0
分析: 我们要赚最多的钱就要把尽可能将所有游戏都完成，尽量舍弃价值小的。我们用一个结构体来储存时间和价值，然后把游戏价值按从大到小进行排序，创建一个flag对游戏完成与否进行标记 代码: #include<iostream> #include<algorithm> #include<cstring> using namespace std; struct set{ int t; int w; bool operator<(const set &rhs)const{ return w>rhs.w; } }; int main() { set a[505]; int m,n,t[505]; memset(t,-1,sizeof(t)); cin>>m; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].t; } for(int i=1;i<=n;i++) { cin>>a[i].w; } sort(a+1,a+1+n); for(int i=1;i<=n;i++) { int flag=0; for(int j=a[i].t;j>=1;j--) { if(t[j]-1) { t[j]=i; flag=1; break; } } if(flag0) { m-=a[i].w; } } cout<<m; }
-
0
Mrnaoketong LV 7 @ 2021-10-14 20:36:14
这里用了一个对组存了一下每个任务的结束时间以及未完成会扣除的钱，要使扣除的钱最少，就必须得优先完成权重大的任务，我的思路是使用一个布尔数组来表示这一天有没有被使用，比如一个任务截止为4，那我就可以使用4之前的任意一天来完成，但是这里注意，**我完成的时候必须从截止日期的那一天开始找，往回找，比如第4天截止，我就要先判断第4天，再判断第三天，不然后面可能会因为存在比如如果我在第四天完成了截止日期为4的任务，那么紧跟着的截止日期为1的任务就还有完成的机会，如果我截止日期为第四天，我却选择第一天来完成，那么我截止日期为1并且权重仅仅小于截止日期为4的任务就无法完成。**如果这个任务没有找到能用来完成的日期，那我就只能将金额扣除 下面还是贴一下代码：
#include <bits/stdc++.h> using namespace std; bool judge [505]; pair<int,int>pa[505]; bool cmp(pair<int,int>a,pair<int,int>b) { return a.second>b.second; } int main() { int m,n; cin>>m>>n; for(int i=1;i<=n;++i)cin>>pa[i].first; for(int i=1;i<=n;++i)cin>>pa[i].second; sort(pa+1,pa+n+1,cmp); for(int i=1;i<=n;++i) { for(int j=pa[i].first;j>=1;j--) { if(judge[j]==false) { judge[j]=true; break; } if(j==1){ m-=pa[i].second; break;} } } cout << m << endl; }
- 1