AcWing 430. 纪念品分组
原题链接
简单
作者:
HiCode_001
,
2019-11-05 23:58:32
,
所有人可见
,
阅读 774
题意:
将所有物品进行分组,使得最后组数最少,其中要求:1)每一组不能超过两件纪念品 2)每一组纪念品价值不超过规定价值
考察知识点:
贪心、排序
时间复杂度:
快速排序nlong 所以O(nlong)
思路分析:
1)将所有的纪念品按照价格进行从下到大排序
2)在不超过组合价值上线下,尽可能让组合的价值大,也就是找到所谓最合适的组合同伴
3)即可求出最小值组数
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30010;
int vi[N];
bool gift[N];
int n,w,res;
int main(){
cin >> w >>n;
for(int i = 0 ; i < n; i++) cin >> vi[i];
sort(vi,vi+n);
for(int i = 0,j = n-1;i<n;i++){
if(gift[i]) continue;
while(j>=i&&(gift[j]||(vi[i]+vi[j]>w))) j--;
gift[i] = gift[j] = true;
res ++;
}
cout << res;
return 0;
}