题解：P1094 [NOIP2007 普及组] 纪念品分组

WsW_ · 2025-01-17 11:05:59 · 题解

思路

每一个纪念品都必须在一个组中。假设我们现在想给 P_i 分组，那么我们一定是找最大的 P_j 满足 P_i+P_j\le w。
如果不是找的最大的 P_j，那么就会导致剩下的纪念品中有一个较小的被换成了较大的，一定不优。
按照这个思路贪心即可，找最大的 P_j 可以利用二分、平衡树、双指针等算法维护。

时间复杂度为 O(n\log n)，瓶颈在于排序。

代码

以下代码使用双指针维护。

#include<bits/stdc++.h>
using namespace std;
int w,n,i,j,sum;
int p[30004];
int main(){
    scanf("%d%d",&w,&n);
    i=1,j=n;
    for(int i=1;i<=n;i++)scanf("%d",&p[i]);
    sort(p+1,p+1+n);
    while(i<=j){
        if(p[j]>w||p[i]>w||(p[i]+p[j])>w){
            sum++;
            j--;
            continue;
        }
        sum++;
        i++;
        j--;
    }
    printf("%d",sum);
    return 0;
}