CF725E Too Much Money
syk666
·
·
题解
首先有一个性质，最优答案加且只用加一枚硬币 。
证明：若需要加两枚硬币 a,b ，钦定 a \ge b
共有三种情况：
$ 2. $ 若当前只用 $ b $ ，同理也不需要 $ a $ 。
$ 3. $ 若当前 $ a,b $ 均用，则到使用 $ a $ 之前，目前的值是 $ \ge a+b $ 的，且至少在使用完 $ b $ 之后，才可能被卡掉，所以对于任意一个 $ b \le x \le a $ ，在这两种情况下，选与被选的情况相同，不产生影响
。
综上，在最优答案下，我们只会恰好加入一枚硬币，否则无解
考虑枚举 $ 1 $ 到 $ c $ 之间的硬币面额，将其加入。
如何检验？我会暴力！但是 $ O(nc) $ 复杂度太炸了。
考虑记录每一个权值的个数，由枚举硬币到枚举硬币面额。
考虑 $ \sum_{1}^{k} = k \times (k+1) \div 2 $ ，所以枚举到的面额的数量为 $ \sqrt(c) $ 级别的，那么总复杂则为 $ O(c\sqrt c) $ 。
代码如下
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int c,n;
int w[N];
set<int> s;
int cnt[N];
vector<int> tmp;
bool check(){
int now=c;
tmp.clear();
while(now&&s.size()){
auto pre=s.upper_bound(now);
if(pre==s.begin()) return true;
pre--;
int need=now/(*pre);
now-=min(need,cnt[*pre])*(*pre);
tmp.push_back(*pre);
s.erase(pre);
}
if(now) return true;
for(int i=0;i<tmp.size();i++){
s.insert(tmp[i]);
}
return false;
}
int main(){
scanf("%d%d",&c,&n);
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
cnt[w[i]]++;
s.insert(w[i]);
}
for(int i=1;i<=c;i++){
s.insert(i);
cnt[i]++;
if(check()){
cout<<i<<endl;
return 0;
}
cnt[i]--;
if(cnt[i]==0) s.erase(s.find(i));
}
cout<<"Greed is good"<<endl;
return 0;
}
```