P1094 纪念品分组
程序员文章站
2022-07-16 12:04:29
...
这道题也是典型的贪心问题,我们要尽可能的找出两对纪念品种(能找两对就不找一对),也就是说价值最小的要尽可能匹配价值大的物品,这样才会使得匹配两对的多,分别设置两个指针,一个从左向右,一个从右向左 AC代码:
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int w,n;
cin>>w>>n;
int a[n+1];
int sum=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
int i=1,j=n;
while(i<=j)
{
if(i==j)
{
sum++;
break;
}
if(a[i]+a[j]<=w)
{
sum++;
i++,j--;
}
else
{
j--;
sum++;
}
}
cout<<sum<<endl;
return 0;
}
上一篇: LeetCode 63. 不同路径 II