P1094 题解

ikunTLE · 2025-01-15 22:00:51 · 题解

题目传送门

思路

可以使用双指针解决此题。

分组可以改变纪念品的顺序，于是先将所有物品按升序排序。因为想让答案尽可能小，最好情况是一个小的纪念品匹配一个大的纪念品。

于是令 l 从 1 向右遍历，r 从 n 向左遍历。若 P_l+P_r\le w，说明编号为 l 和 r 的两个纪念品可以组成一组，就让 l\gets l+1，r\gets r-1。否则说明 P_r 较大，只能单独一组，就让 r\gets r-1。无论哪种情况，都会成为新的分组，就让答案加 1。当 l>r 时需要终止循环。最终输出答案即可。

由于 l 和 r 都会向着自己的方向遍历而不后退，故时间复杂度为 \mathcal{O}(n\log n)（排序），可以通过此题。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=3e4+10;
int a[N];
int main(){
    int w=read(),n=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    sort(a+1,a+n+1);
    int l=1,r=n,ans=0;
    while(l<=r){
        if(a[l]+a[r]<=w)
            ++l;
        --r,++ans;
    }
    printf("%d\n",ans);
    return 0;
}