1107纪念品分组(sort排序加指针移动）

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<algorithm>

using namespace std;

bool cmp(int p1, int p2)

{

return p1 < p2;

}

int main()

{

int max;//价钱的上限

cin >> max;

int n;//商品个数

cin >> n;

//这里要开大一点，题目没有明确给出来，我试了好几次才找到30000的，10000是过不去的！！！

int a[30000];//存商品价钱

for (int i = 1; i <= n; i++)

{

cin >> a[i];

}

//将价钱从小到大排序

sort(a + 1, a + n + 1, cmp);

//上面排完序后，lift就指向小的价钱，也就是第一个元素

//rigt就指向大的价钱，也就是最后一个元素

int* lift = a+1;

int* rigt = a + n;

int count = 0;//记录数量

//下面的思路就是，先将最接近上限的两件物品选出来，并将它们的值赋为0

//移动的话只要移动指针的位置就行

//这时，肯定存在没有匹配成功的物品，而它们的值肯定不为0，后面我们就可以利用这一点

while(lift<rigt)

{

if ((*lift ) + (*rigt) <= max)

{

(*lift) = 0;

(*rigt) = 0;

count++;

lift++;

rigt--;

}

if ((*lift ) + (*rigt) > max)

{

rigt--;

}

}

//这里我们通过遍历，找到不为0的数，让数量加一，就可以得到最后的数量啦

for (int i = 1; i <= n; i++)

{

if (a[i] != 0)

{

count++;

}

}

cout << count;

return 0;

}