NC16640. [NOIP2007]纪念品分组
描述
输入描述
第 1 行包括一个整数 w，为每组纪念品价格之和的上限。
第 2 行为一个整数n，表示购来的纪念品的总件数。
第 3 ~ n+2 行每行包含一个正整数 pi ( 5 ≤ pi ≤ w ) ，表示所对应纪念品的价格。
输出描述
包含一个整数，即最少的分组数目。
示例1
输入:
100 9 90 20 20 30 50 60 70 80 90
输出:
6
C++ 解法, 执行用时: 13ms, 内存消耗: 616K, 提交时间: 2021-07-08 12:24:19
#include<bits/stdc++.h>
using namespace std;
int w,n,L,R,a[3000000],u=0;
int main()
{cin>>w>>n;
for(int i=0;i<n;i++)
cin>>a[i];
L=0;R=n;
sort(a,a+n);
while(L<=R)
{if(a[L]+a[R]<=w) L++;
R--;u++;
}
cout<<u-1;
}
C++14(g++5.4) 解法, 执行用时: 8ms, 内存消耗: 528K, 提交时间: 2020-10-07 20:54:21
#include<bits/stdc++.h>
using namespace std;
int w,n,i,j,s,a[30001];
main()
{
cin>>w>>n;
for(;i<n;i++)cin>>a[i];
sort(a,a+n);
for(n--;j<=n;n--)
{
if(a[j]+a[n]<=w)j++;s++;
}cout<<s;
}
Python3 解法, 执行用时: 132ms, 内存消耗: 4944K, 提交时间: 2022-03-05 16:53:55
w=int(input())
n=int(input())
p=[int(input())for i in range(n)]
p.sort()
s=0
while p:
if p[0]+p[-1]<=w and len(p)>1:
p.pop(0)
p.pop(-1)
s+=1
print(s)