luogu P8444 不等价交换法则

题目传送门

分析

仔细审了题面，猜想是贪心模拟，下面给出证明：

因为只能用元买一个商品，所以要挑贵的买（越贵，换得的商品越多），后令商品尽可能的去换低价格的商品，即把手头所有的商品能换就换，则最后换来的商品总价值一定不会超过第一次买的商品，而且随着不断的交换，你商品的总价值只会下降而不会升高，不论如何，你第一次买的商品价值一定是最高的，价值越高，换来的商品就越多，只需第一次买的商品就能得到最终答案。

代码实现：先进行快排(从小到大），找到最大价值的商品，
标记后退出循坏，如果 \(t>0\) ，则从小到大排序，再进行交换商品。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long a[N],n,w,t=0,ans=0;//开long long！
inline bool cmp(int x,int y){
	return x>y;//从大到小排序
}
inline bool cmp1(int x,int y){
	return x<y;//从小到大排序
}
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	scanf("%lld",&w);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;++i){
		if(t==0)
			if(w-a[i]>=0){
				w-=a[i];//减去最大值
				t=a[i];//标记
				break;//退出循环
			}
	}
	if(t){
		sort(a+1,a+n+1,cmp1);
		for(int i=1;i<=n;++i){
			if(t>=a[i]){
				t-=a[i];
				ans++;//累计答案
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}