贪心求hack，给出证明过程（但不知是否严谨）

该做法通过了考场大样例但是写挂了被一颗都不买的数据干掉了~~小 M 怎么这么穷~~。

涉及可能的正解故折叠

注意到：购买方式一定为：购买一些种类糖果的第一颗和购买总价最小的一种糖果的若干组，其中总价指购买两颗该种类糖果的价格。

证明：如果购买两种总价不同的糖果各一组，则将其中一组换成总价更低的一组糖果，其价值不变且代价更少。

于是考虑选择哪些糖果只购买一颗，由于所有糖果的价值相同，所以直接排序即可。

CPP

12345678910111213141516171819202122232425262728293031323334353637#include<iostream>
#include<algorithm>
using namespace std;

long long n,m,ans;

struct Candy{
	long long x,y;
	bool operator < (const Candy &c) const
	{
		return x < c.x;
	}
}c[100005];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	long long sum = 0,mn = 0x3f3f3f3f3f3f3f3f;
	for(int i = 1;i <= n;i += 1)
	{
		cin>>c[i].x>>c[i].y;
		mn = min(mn,c[i].x + c[i].y);
	}
	sort(c + 1,c + 1 + n);
	for(int i = 0;i <= n;i += 1)
	{
		sum += c[i].x;
		if(sum > m)
		{
			break;
		}
		ans = max(ans,(m - sum) / mn * 2 + i);
	}
	cout<<ans;
	return 0;
}

贪心求hack，给出证明过程（但不知是否严谨）

讨论操作

回复

相关推荐

贪心求hack，给出证明过程（但不知是否严谨）