AcWing 430. 纪念品分组(双指针+贪心)
原题链接
简单
作者:
逸误
,
2024-04-10 13:51:06
,
所有人可见
,
阅读 7
//贪心:先排个序,每次先放最小的,再找一个最大可以和他匹配的
//如果是先放最大的,会发现没法双指针,而需要O(n^2),不行
//先放小的,可以使右边指针保证从大到小走,双向跑一遍,O(n)
//证明:考虑贪心解与最优解第一个分组不同的数a,则有
//如果在最优解中,a单独一组,那么可以直接将b从原组中取出,和a放在一起,这样并没有增加组数;
//如果在最优解中,a和c放在一起,由上述算法可知,c≤b,那么我们可以将b和c所在位置交换,交换后两组的价值之和都没有超过上限,且这样也没有增加组数。
//如此一直操作可以使贪心解转化为最优解,组数也还是不变
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30005;
int w,n;
int a[N];
bool st[N];//分组过没有
int res;
int main()
{
cin>>w>>n;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
for(int i=1,j=n;i<=n;i++)//双指针!
{
//这步,考虑第i个数可以和哪个最大的第j个数组成一组
if(st[i])
continue;
//i保证是未配对的里面最小的数
while(j>=i&&(st[j]||a[i]+a[j]>w))
{
j--;
}
//走到这里就找到了最大的和i匹配的未配对的j
st[i]=st[j]=true;
res++;
}
cout<<res<<endl;
return 0;
}