不要怀疑,就是贪心
by _l_l_l_l_l_ @ 2021-09-25 17:37:52
@[WenZKbb](/user/522828) 求大佬指点QWQ
by pencil @ 2021-09-25 17:41:52
@[pencil](/user/137723)
这题好久之前做的,忘的差不多了，所以就把代码扔出来吧 里面有注释
```
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int m,n;
bool vis[505]={false};//vis[i]--第i个时间段用没用
struct riddle
{
int t,w;
}a[505];
bool cmp(riddle x,riddle y)
{
if(x.w!=y.w)return x.w>y.w;
return x.t<y.t;
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i].t);
for(int i=1;i<=n;i++)
scanf("%d",&a[i].w);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
bool done=false;//这个任务能否完成
for(int j=a[i].t;j>=1;j--)//贪心策略:尽量在晚完成,为前面腾出时间
{
if(!vis[j])//放在j做
{
vis[j]=1;
done=1;
break;
}
}
if(!done)
m-=a[i].w;//接受惩罚
}
if(m<0)
m=0;
printf("%d\n",m);
return 0;
}
```
by _l_l_l_l_l_ @ 2021-09-25 17:44:15
@[pencil](/user/137723)
```cpp
#include <bits/stdc++.h>
using namespace std;
#define MAXN 505
#define MAXH 5005
int m, n;
bool vis[MAXN];
struct node {
int t, w;
} a[MAXN];
bool cmp(node a, node b) {return a.w > b.w;}
int main(){
cin >> m >> 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, cmp);
for (int i = 1; i <= n; i++) {
for (int j = a[i].t; ; j--) {
if (!j) {
m -= a[i].w;
break;
}
if (!vis[j]) {
vis[j] = 1;
break;
}
}
}
cout << m << endl;
return 0;
}
```
by liuzimingc @ 2021-09-26 14:06:01
hihi
by zhubin2021 @ 2022-07-13 18:45:00
可以反悔贪心
优先做时间短的 时间相同的优先做扣的钱数多的。发现更优就反悔
by hyf9134 @ 2022-07-26 21:52:50