纪念品分组 （C++代码）贪心的方法

解题思路:

//贪心的思想： 把最大的和最小的相加 如果大于了 那么最大的那个 只能单独一个组

// 然后最小的再跟第二大的  如果不大于  那么就组成一个组 然后赋值为0  然后第二小的继续

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define ll long long 

#define MAX 1000000

int a[MAX];

int main()

{

int cnt, n;

cin >> cnt >> n;

for (int i = 0; i < n; ++i) {

cin >> a[i];

}

sort(a, a + n);

int num=0,sum=0;

//贪心的思想： 把最大的和最小的相加 如果大于了 那么最大的那个 只能单独一个组

// 然后最小的再跟第二大的  如果不大于  那么就组成一个组 然后赋值为0  然后第二小的继续

int l = 0, r = n-1;

while (l <= r)

{

if (a[l] + a[r] <= cnt&&a[l]!=0&&a[r]!=0) {

num++;

a[l] = 0;

a[r] = 0;

r--;

l++;

}

else {

a[r] = 0; //单独一个一个组

num++;

r--;

}

}

cout << num << endl;

//system("pause");

return 0;

}