不能超过……不是少于

把数列排序，然后从最大的看，如果没取过的最大的和没取过的最小之和可以放下，就放，要不然就只放没去过的最大的。

#include<bits/stdc++.h>
using namespace std;
int a[100001];
int main()
{
    int ans=0,i,j,k=0,l,n,m;
    cin>>m>>n;
    l=n-1;
    for(i=0;i<n;i++) cin>>a[i];
    sort(a,a+n); 
    for(i=0;i<n;) {
        if(a[k]+a[l]<=m) k++,l--,i+=2;
        else l--,i++;
        ans++;
    } 
    cout<<ans<<endl;
    return 0;
}

sort排序之后就可以用下面这种方法了：
优先选择最大的物品，如果可以放下一个较小的，放；
如果无法放下那个较小的物品，放弃放入这个较小的物品。
贪心思想：在maxk之内使两个物品的w值之和最大
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
const int num = 30005;
int k[num];
int main() {
int n,maxk; cin >> maxk >> n;
for(int i = 0;i < n;i++)
cin >> k[i];
sort(k,k + n);
int temp = 0,x = n - 1;
int ans = 0;
while(temp <= x) {
if(k[x] + k[temp] <= maxk) {
ans++;
x--; temp++;
}
else {
ans++; x--;
}
}
cout << ans << endl;
return 0;
}

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

int W,ans=0;
int n,a[30001];
int l,r,i;
int main()
{
    scanf("%d%d",&W,&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    l=1;  r=n;
    while(l<=r)
    {
        if(a[l]+a[r]<=W)   
            l++,r--,ans++;
        else
            r--,ans++;  
    }
    printf("%d",ans);
    return 0;
}

a=[]
def sorta(l,r):
    i=l
    j=r
    mid=a[int((l+r)/2)]
    while i<j:
        while a[i]<mid:
            i=i+1
        while mid<a[j]:
            j=j-1;
        if i<=j:
            tmp=a[i]
            a[i]=a[j]
            a[j]=tmp
            i=i+1
            j=j-1
    if l<j:
        sorta(l,j)
    if i<r:
        sorta(i,r)
w=int(input())
def calc(l,r):
    i=l
    j=r
    ans=0
    while i<j:
        ans=ans+1
        if a[i]+a[j]<=w:
            i=i+1
            j=j-1
        elif a[i]<a[j]:
            j=j-1
        else:
            i=i+1
    if i==j:
        ans=ans+1
    return ans
n=int(input())
for i in range(0,n):
    a.append(int(input()))
sorta(0,n-1)
print(calc(0,n-1))

排序，如果最大最小之和不超过上限，则为一组。
否则，最大的自成一组。

#include<iostream>
using namespace std;
int main()
{
    int max, N, num[30000], group = 0;
    cin >> max >> N;
    int i, j;
    for (i = 0; i < N; i++)cin >> num[i];
    for (i = 0; i < N - 1; i++)for (j = i + 1; j < N; j++)if (num[i] > num[j])
    {
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    i = 0; j = N - 1;
    while (i <= j) {
        if (num[i] + num[j] <= max) {
            group++;
            i++;
        }
        else group++;
        j--;
    }
    cout << group;
    return 0;
}

因为要经常进行头和尾部的操作，所以数据结构选择了deque，两头都能操作的queue。

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

int main(int argc, char *argv[]) {
#ifdef DEBUG
    freopen("a.in", "r", stdin);
#endif
    int limit, n, x, r = 0;
    deque<int> l;
    cin >> limit >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x;
        l.push_back(x);
    }
    sort(l.begin(), l.end());
    while (l.size() > 1) {
        r++;
        if (l.back() + l.front() <= limit)
            l.pop_front();
        l.pop_back();
    }
    cout << r + l.size() << endl;
    return 0;
}

这题看似很难，本质在于 每组数量不超过\(2\)

显然只需要用\(two\) \(pointers\) ，也就是双指针，尺取法。

先排序，指针一头一尾。每次看最大的和最小的能不能成一组，不能则 把最大作为一组，尾指针\(---\) ，否则两个一组，尾指针\(--\)，头指针\(++\).每次计数。

贪心策略。

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

int w,n,s=0;
int l,r,a[30001];

inline int read(){char ch=getchar();while(ch<'0' || ch>'9') ch=getchar();
    int x=0;while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x;}

int main(){
    w=read(),n=read(); for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+1+n);
    l=1,r=n;
    while(l<=r){
        if(a[l]+a[r]<=w) l++,r--;
        else r--;
        s++;
    }
    if(l==r) s++;
    printf("%d",s);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int W,ans=0;
int n,a[30001];
int l,r,i;
int main()
{
    scanf("%d%d",&W,&n);
    for(i=1;i<=n;i++)
      scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    l=1;  r=n;
    while(l<=r)
    {
        if(a[l]+a[r]<=W)
          l++,r--,ans++;
        else
          r--,ans++;
    }
    printf("%d",ans);
    return 0;
}

水水水......
直接贴代码吧：
#include<cstdio>
#include<algorithm>
using namespace std;
int a[30005];
int main()
{
int w,n,s=0;
scanf("%d %d",&w,&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
int x=1,y=n;
while(x<=y)
{
if(a[x]+a[y]<=w)
{
x++;
y--;
s++;
}
else
{
y--;
s++;
}
}
printf("%d\n",s);
return 0;
}

/*
思路：先按大小排个序，保证开头末尾是最大或最小的，只要循环一遍不会超时
从最大的开始往回，如果最小的能和它配成一组就配，配不成大的就单独一组
代码如下
*/
#include <cstdio>
#include <algorithm>
using namespace std;
int a[30001];
int main()
{
int ans=0,n,w;
scanf("%d",&w);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);//排序
int min=1,i; //设i变量便于判断是否有最后一个需单独分组，min表示当前最小价值
for(i=n;i>min;i--) //i从最大的开始，直到匹配到min前
{
if((a[i]+a[min])<=w) //如果当前最大加当前最小小于w可分组
{
min++;
ans++;
// printf("第%d组：%d %d\n",ans,a[i],a[min]);
continue; //分组成功后跳过本次循环
}
ans++; //单独分组
// printf("第%d组：%d\n",ans,a[i]);
}
// printf("%d %d\n",i,min);
if((min-1)!=i)ans++; //22行里的min++的缘故，这里是min-1而不是min
printf("%d\n",ans);
return 0;
}
//20 20 30 50 50 60 70 80 90 90
//1 2 3 4 5

这题没啥难度，可能唯一的难点是 不超过max，不是小于max ..

#include <stdio.h>
#include <stdlib.h>
int cmp(const void* a,const void* b){
    return *(int *)b-*(int *)a;
}
int main(int argc, char* argv[])
{
    int max,n,i;
    scanf("%d%d",&max,&n);
    int price[30000];
    for(i=0;i<n;i++)
        scanf("%d",&price[i]);
    qsort(price,n,sizeof(int),cmp);
    int total=0;
    for(i=0;i<n;i++){
        if(price[i]==-1)continue;
        //暴力遍历寻找能与其匹配在一组里的最大值
        int j;
        for(j=i+1;j<n;j++){
            if(price[j]==-1)continue;
            if(price[j]+price[i]<=max){
                total++;
                price[j]=price[i]=-1;
                break;
            }
        }
        if(price[i]!=-1){
            total++;
            price[i]=-1;
        }
    }
    printf("%d",total);
    return 0;
}

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,w;
int a[30017];
int cmp(int x,int y)
{
return x>y;
}
int main()
{
cin>>w>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1,cmp);
int cnt=0;
for(int i=1;i<=n;i++)
{
if(a[i]<=w&&a[i]!=0)
{
int p=w-a[i];
for(int j=i+1;j<=n;j++)
{
if(a[j]<=p&&a[j]!=0)
{
a[j]=0;
break;
}
}
cnt++;
}
}
cout<<cnt<<endl;
return 0;
}

#include <iostream>
#include<algorithm>
using namespace std;
#define size 50001
int a[size];
int n,m;
int main()
{
cin>>n>>m; //n是上限 m是个数
for(int i=1;i<=m;i++)
{
cin>>a[i];
}
sort(a,a+m+1);
int sum=0;
int x=1,y=m; //从"最短的"和"最长的"分头比
while(x<=y)
{
if(x==y) //如果i==j代表他们重合了 这时除了这一个其他的都已经遍历过了 那么加上这一后 结束就行了

{
sum++;
x++;
y--;
break;
}
if(a[x]+a[y]<=n)
{
sum++;
x++;
y--;
}
else if(a[x]+a[y]>=n) //代表这个短边加上这个长边后会越界 那么就让长边自己一组(j--)但是短边继续等着 和下一个长边比比看

{
sum++;
y--;
}
}
cout<<sum<<endl;
return 0;
}

include <iostream>

include <vector>

include <algorithm>

using namespace std;
int solution(vector<int> gift, int line)
{
make_heap(gift.begin(), gift.end());
sort_heap(gift.begin(), gift.end());
vector<int>::iterator it1=gift.begin(),it2=gift.end()-1;
int sum = 0;
while (it1 != it2&&it1<it2)
{
if ((*it1) + (*it2) <= line)
{
sum++;
it1++;
it2--;
}
else
{
it2--;
sum++;
}
}
if (it1 == it2)
sum++;
return sum;
}

int main()
{
int Line,n,a;
vector<int> Gift;
cin >> Line;
cin >> n;
for (int i = 0;i <= n - 1;i++)
{
cin >> a;
Gift.push_back(a);
}
cout << solution(Gift, Line);
return 0;
}

贪心算法

#include <iostream>
#include <algorithm>
using namespace std;

int w, n;
int M[30001];

bool cmp(int a, int b)
{
    return a > b;
}

int main()
{
    cin >> w >> n;
    for (int i = 0; i < n; i++)
        cin >> M[i];
    sort(M, M + n, cmp);
    int i, j = n - 1;
    for (i = 0; i <= j; i++)
    {
        int k = M[i];
        while (k + M[j] <= w && i != j)
        {
            k += M[j];
            j--;
        }
    }
    cout << i << endl;

    return 0;
}

python

items = []
groups = 0

top_wealth = int(input())
n = int(input())
for i in range(0, n):
    items.append(int(input()))

items.sort(reverse=True)
###由大到小排序

j = -1
for i in range(0, n):
### i-j=n 时，指针i和指针j指向同一物品
    if i - j == n:  
        groups += 1
        break
    if i - j < n:
        if items[i] + items[j] <= top_wealth:
            groups += 1
            j = j-1
        else:
            groups += 1

print(groups)

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q1;
priority_queue<int,vector<int>,less<int> >q2;
int w,n,ans=0,a,tot;
int main()
{
cin>>w>>n;
tot=n;
for(int i=0;i<n;i++)
{
cin>>a;
q1.push(a);
q2.push(a);
}
while(tot>0)
{
int s1=0,s2=0,m;
s1=q1.top();
q1.pop();
s2=q2.top();
q2.pop();
if(s1+s2>w)
{
ans++;
tot--;
q1.push(s1);
}
else
{
ans++;
tot-=2;
}
}
cout<<ans;
}

//直接AC 爽！
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int w,n; cin>>w>>n;
    int a[n];
    for(int i=0;i<n;++i) cin>>a[i];
    sort(a,a+n);
    int l=0,r=n-1,res=0;
    while(l<=r){
        if(a[r]>w) {++res; --r;}
        else{
            if(a[l]+a[r]>w){
                ++res; --r;
            }else{
                ++res; ++l; --r;
            }
        }
    }
    cout<<res;
    return 0;
}

水水水，直接贴吧。

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

int main()
{
int w;//w为每组纪念品价格之和的上限
int n;//n为购买来的纪念品的总和
cin>>w>>n;
int a[n];//用于储存n个纪念品的价格
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a,a+n);//从小到大排序
int counter=0;//用于计量当前一组的纪念的价格
int sum=0;//定义所分的组数
int mount=0;//定义一组中的礼物的数量
int x;//作为中间的储存变量
int index=n;//用于记录还剩余多少个礼品未被分组
while(index>0){
int i;
for(i=n-1;i>=0;i--){//开始循环判断是否大于礼品的金额
if(a[i]!=0){
counter=counter+a[i];
mount++;
x=a[i];
a[i]=0;
}
if(counter>w){//如果结果大于100则返回原来的状态
counter=counter-x;
mount--;
a[i]=x;
}
if(mount==2&&counter<=w){//满足条件的一种退出方式
index=index-2;
sum++;
counter=0;
mount=0;
break;
}
}
if(i==-1){//如果到最后还没有合适的则跳出，单独分为一组
sum++;
index--;
counter=0;//把计数器都清零
mount=0;
}
}
cout<<sum<<endl;//输出结果
return 0;
}

#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;

int main()
{
    int limit;
    int n;
    cin>>limit>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
    int residue=n;
    int ans=0;
    for(int i=0,j=n-1;residue>0;)
    {
        if(i==j)
        {
            ans++;
            break;
        }
        else if(a[i]+a[j]<=limit)
        {
            i++;
            j--;
            residue-=2;
            ans++;
        }
        else
        {
            j--;
            residue--;
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}