洛谷 P1094 [NOIP2007 普及组 T2]：纪念品分组 ← 贪心+排序

【题目来源】
https://www.luogu.com.cn/problem/P1094
https://www.acwing.com/problem/content/432/

【题目描述】
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

【输入格式】
共 n+2 行：
第一行包括一个整数 w，为每组纪念品价格之和的上限。
第二行为一个整数 n，表示购来的纪念品的总件数 G。
第 3∼n+2 行，每行包含一个正整数 Pi，表示所对应纪念品的价格。

【输出格式】
一个整数，即最少的分组数目。

【输入样例】
100 
9 
90 
20 
20 
30 
50 
60 
70 
80 
90

【输出样例】
6

【说明/提示】
50% 的数据满足：1≤n≤15。
100% 的数据满足：1≤n≤3×10^4，80≤w≤200，5≤Pi≤w。

【算法分析】
● 贪心算法
（1）将所有纪念品按价格从小到大进行排序；
（2）从小到大枚举每个纪念品：每次给当前纪念品找一个价格尽可能大且总价格没有超过上限的纪念品，将两个纪念品分在一组。此步可以使用双指针算法优化到 O(n)；
（3）依据上述两步求出的分组数目就是最小值。

● 双指针算法
（1）双指针算法，顾名思义就是使用两个指针（实践中常用两个变量来模拟双指针）来解决问题。这两个指针通常从数组/链表的两端或者一端开始移动，逐步缩小搜索范围，直到找到满足条件的解。
（2）双指针算法是一种非常实用且常见的算法技巧，在解决各种类型的问题中都有广泛应用。相比于暴力枚举法，双指针算法往往具有更优的时间复杂度。
（3）双指针算法的常见类型
在同一个序列中，用两个指针维护两个位置，或两个位置包含的区间；
在两个序列里边，两个指针指向不同的序列，来维护某种次序。
（4）双指针类型
按照指针的移动方向，双指针分为同向双指针、异向双指针。
同向双指针，也称快慢指针（两个指针一快一慢）；
异向双指针，分为对撞指针（从两边向中间移动）、背向指针（从中间向两边移动）。

【算法代码】

#include<bits/stdc++.h>
using namespace std;

const int N=3e4+5;
bool st[N];
int val[N];
int w,n;

int main(){
    cin>>w>>n;
    for(int i=0;i<n;i++) cin>>val[i];

    sort(val,val+n);

    int ans=0;
    for(int i=0,j=n-1;i<n;i++){ //Two-pointer algorithm --> i=0,j=n-1
        if(st[i]) continue;
        while(j>=i && (st[j] || val[i]+val[j]>w)) j--;
        st[i]=st[j]=true;
        ans++;
    }
    cout<<ans<<endl;
    
    return 0;
}

/*
in:
100
9
90
20
20
30
50
60
70
80
90

out:
6
*/

【参考文献】
https://www.luogu.com.cn/problem/solution/P1094
https://www.acwing.com/solution/content/4522/
https://blog.csdn.net/weixin_39145520/article/details/134889410
https://www.cnblogs.com/luwei0424/p/17810978.html