（还有既然O(n^2)算法能过的话把难度调为橙是不是更合适一些）
by vectorwyx @ 2020-08-13 09:05:34
~~这种水题不差这一个难度吧(~~
by 血色黄昏 @ 2020-08-13 09:16:53
啊这，我们校OJ有数据加强版，用并查集优化贪心
by Prean @ 2020-08-13 09:44:11
@[limaopipi2022](/user/160839) ？！
by vectorwyx @ 2020-08-13 11:21:43
@[limaopipi2022](/user/160839) 能说一下怎么用并查集优化吗QAQ，我只会用堆优化，菜死了/kk
by vectorwyx @ 2020-08-13 11:22:44
@[vectorwyx](/user/238408) 用并查集维护时间
by Prean @ 2020-08-13 11:23:18
@[mrsrz](/user/6813)
请求将此题降橙并添加数据加强版QAQ
by vectorwyx @ 2020-08-13 11:25:18
@[limaopipi2022](/user/160839) 额？维护哪些时间啊QAQ
by vectorwyx @ 2020-08-13 11:26:08
@[vectorwyx](/user/238408) 贪心是按照价值排序，然后从时间往开头找，找到第一个没有占用的时间嘛
就是用并查集优化找的过程
by Prean @ 2020-08-13 11:28:54
并查集维护：
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e6+6;
int m,n,f[N],sum,ans;
bool flag;
struct Node{
int d,s;
bool operator<(const Node &B){
return s>B.s||(s==B.s&&d<B.d);
}
}a[N];
void Build(int n){
for(int i=1;i<=n;++i) f[i]=i;
}
int Find_Change(int p){
if(p<=0) return 0;
else if(f[p]!=p) f[p]=Find_Change(f[p]);
else if(f[p]==p){
f[p]=p-1;
flag=1;
return f[p];
}
}
int main(){
cin>>m>>n;
for(int i=1;i<=n;++i) cin>>a[i].d;
for(int i=1;i<=n;++i){
cin>>a[i].s;
sum+=a[i].s;
}
Build(n);
sort(a+1,a+n+1);
for(int i=1;i<=n;++i){
flag=0;
int re=Find_Change(a[i].d);
if(flag) ans+=a[i].s;
}
cout<<m-(sum-ans);
return 0;
}
```
by Christophe_ @ 2021-12-19 20:48:44