先排序
从小枚举到大
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int w,n,p[30001];
bool used[30001];
int main()
{
scanf("%d%d",&w,&n);
for(int i=1;i<=n;i++)scanf("%d",&p[i]);
sort(p+1,p+n+1);
int ans=0;
for(int i=1;i<=n;i++)
{
if(!used[i])
{
used[i]=1;int x=w;
for(int j=n;j>0;j--)
{
if(!used[j]&&p[i]+p[j]<=x){used[j]=1;x-=p[j];break;}
}
ans++;
}

}
printf("%d",ans);
}
```

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[30010];
int mark[30010];
int main(){
int w,n;
scanf("%d%d",&w,&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
int l=1,r=n,ans=0;
while(r>=l){
if(a[r]+a[l]<=w){
l++;r--;ans++;
}
else{
r--;ans++;
}
}
printf("%d",ans);
return 0;
}

贪心，每次 一个可用最大的配上一个可用最小的 ，配不了的单独为一组
bool数组isUsed储存可用状态

#include <iostream>
#include <algorithm>
using namespace std;
int w,n,a[30000],ans;
bool isUsed[30000];
int main()
{
    cin>>w>>n;
    for(int i=0;i<=n-1;i++)
        cin>>a[i];
    sort(a,a+n);
    for(int i=n-1;i>=0;i--)
        if(!isUsed[i]&&a[i]<w)
            for(int j=0;j<=i-1;j++)
                if(a[i]+a[j]<=w&&!isUsed[j])
                {
                    isUsed[i]=1;
                    isUsed[j]=1;
                    ans++;
                    break;
                }
    for(int i=n-1;i>=0;i--)
        if(!isUsed[i])
            ans++;
    cout<<ans;
    return 0;
}

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int compare(int a,int b)
{
return a>=b;
}
int main()
{
int a[30000];
int w,n,t=0;;
cin>>w>>n;
memset(a,0,sizeof(a));
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n,compare);
int m=0;
for(int i=0;i<n;i++)
{
if(a[i]==-1)
continue;
for(int j=i+1;j<n;j++)
{
if(a[i]+a[j]<=w&&a[i]!=-1&&a[j]!=-1)
{
t++;
a[j]=-1;
m++;
break;
}
}
}
t=t+(n-2*m);
cout<<t<<endl;
return 0;
}

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int compare(int a,int b)
{
return a>=b;
}
int main()
{
int a[30000];
int w,n,t=0;;
cin>>w>>n;
memset(a,0,sizeof(a));
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n,compare);
int m=0;
for(int i=0;i<n;i++)
{
if(a[i]==-1)
continue;
for(int j=i+1;j<n;j++)
{
if(a[i]+a[j]<=w&&a[i]!=-1&&a[j]!=-1)
{
t++;
a[j]=-1;
m++;
break;
}
}
}
t=t+(n-2*m);
cout<<t<<endl;
return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int w = scanner.nextInt();
        int n = scanner.nextInt();
        int prices[] = new int[n];
        for(int i = 0; i < n; i ++){
            prices[i] = scanner.nextInt();
        }
        scanner.close();
        quickSort(prices, 0, prices.length-1);
        int size = 0,sum = 0,used = 0,k = 0;
        for(int i=prices.length-1;i>=0;i--){
            if(used == prices.length)
                break;
            
            used ++;
            
            if(k < i){
                sum = prices[i] + prices[k];
                if(sum <= w){
                    used ++;
                    k ++;
                }
            }
            
            size ++;
            sum = 0;
        }
        System.out.println(size);
    }
    
    //快排
    private static void quickSort(int[] list, int start, int end){
        if(start < end){
            int n = random_partition(list, start, end);
            quickSort(list, start, n-1);
            quickSort(list, n+1, end);
        }
    }
    
    //随机抽取一个，放到最后一位
    private static int random_partition(int[] list, int start, int end){
        int i = (int) (Math.random()*(end-start)) + start;
        int n = list[i];
        list[i] = list[end];
        list[end] = n;
        return partition(list, start, end);
    }
    
    //找到最后一位应该放置的位置，使其不大于后面的数，不小于前面的数
    private static int partition(int[] list, int start, int end){
        int element = list[end];
        int n = start;
        for(int i=start; i<end; i++){
            if(list[i] < element){
                int j = list[i];
                list[i] = list[n];
                list[n] = j;
                n ++;
            }
        }
        list[end] = list[n];
        list[n] = element;
        return n;
    }
}

破题

从两头开始枚举，编号分别设为i，j
注意中间可能出现一次一个单个的，所以循环条件为j>=i；
```
c++
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 30000 + 5;
int w, n, sum = 0, a[maxn];
int main(){
cin >> w >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int j = n, ans = 0;
for(int i = 1; i <= n; i++){
while(j >= i){
ans++;
if(a[i] + a[j] <= w){ j--; break;}
j--;
}
}
cout << ans;
return 0;

}
```

#include <cstdio>
#include <algorithm>

int main(){
// freopen("in.txt","r",stdin);
int n,v,a[30010];
scanf("%d%d",&v,&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
std::sort(a+1,a+n+1);

int p=n,ct=0,flag;
for(int i=1;i<p;i++){
do{
flag=1;
if(a[i]+a[p]<=v){
ct++;
flag=0;
}
p--;
}while(flag&&i<p);
}
printf("%d",n-ct);

return 0;
}

这不是传说中的乘船问题
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int a[30000+3];
int main(){
int m,n;
cin>>m>>n;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n);
int l=0,r=n-1,ans=0;
while(l<=r){
if(a[l]+a[r]<=m&&l<r){ans++;l++;r--;}
else {ans++;r--;}
}
cout<<ans;
return 0;
}

var w,n,i,j,t:longint;
a:array[1..30000] of longint;
procedure ps(h,t:longint);
var i,j,mid,k:longint;
begin
i:=h; j:=t; mid:=a[(h+t) div 2];
repeat
while a[i]<mid do inc(i);
while a[j]>mid do dec(j);
if i<=j then
begin
k:=a[i]; a[i]:=a[j]; a[j]:=k;
inc(i); dec(j);
end;
until i>j ;
if h<j then ps(h,j);
if i<t then ps(i,t);
end;
begin
readln(w);
readln(n);
for i:=1 to n do
readln(a[i]);
ps(1,n);
i:=1; j:=n;
while i<j do
begin
if a[i]+a[j]<=w then
begin
inc(i);
dec(j);
t:=t+1;
end else
dec(j);
end;
writeln(n-t);
readln;
end.

program jnp;
var
a:array[1..30000] of longint;
n,w,i,j,t,s,x:longint;
procedure qsort(l,r:longint);
var
i,j,m,p:longint;
begin
i:=l;
j:=r;
m:=a[(l+r) div 2];
repeat
while a[i]<m do
inc(i);
while a[j]>m do
dec(j);
if i<=j then
begin
p:=a[i];
a[i]:=a[j];
a[j]:=p;
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
procedure ps;
begin
for i:= 1 to n-1 do
for j:= i+1 to n do
begin
if a[i]>a[j]
then begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
end;
end;
begin
readln(w);
readln(n);
s:=0;
for i:= 1 to n do
begin
readln(a[i]);
end;
//qsort(1,n);
ps;
{ for i:= 1 to n do
write(a[i]:4);
writeln; }
{ for i:= 1 to n-1 do
for j:= n downto i+1 do
begin
x:=a[i]+a[j];
if x<w
then
begin
inc(s);
end;
end;}
i:=1;
j:=n;
while i<j do
begin
if a[i]+a[j]<=w
then
begin
inc(s);
inc(i);
dec(j);
end
else
begin
//inc(i);
dec(j);
end;
// end;
end;
writeln(n-s);
readln
end.

随便写个乱七八糟的贪心竟然AC了！！
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int N = 201;
int w,n,t,s = 0,P[N];
int main()
{
scanf("%d%d",&w,&n);
memset(P,0,sizeof(P));
for(int i = 0;i < n;i++)
{
scanf("%d",&t);
if(t <= w) P[t]++;
}
for(int i = 1;i <= w;i++)
while(P[i])
for(t = w - i;;t--)
{
if((P[t] && t != i) || (P[t] > 1 && t == i))
{
P[i]--;P[t]--;s++;
break;
}
if(t <= 0)
{
P[i]--;s++;
break;
}
}
printf("%d\n",s);
return 0;
}

水到极致
测试数据 #0: Accepted, time = 0 ms, mem = 920 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 920 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 916 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 916 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 920 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 916 KiB, score = 10
Accepted, time = 45 ms, mem = 920 KiB, score = 100

program ac;
var a:array[1..30000]of longint;
i,j,k,ans,w,n,t,x:longint;

procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while a[i]<x do
            inc(i);
           while x<a[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

begin
  readln(w,n);
  ans:=0;x:=0;
  for i:=1 to n do readln(a[i]);
  sort(1,n);
  i:=1;j:=n;
  while i<j do
  begin
    if a[i]+a[j]<=w then
    begin
      i:=i+1;
      j:=j-1;
      inc(ans);
    end
    else begin j:=j-1;inc(ans);x:=x+1;end;
  end;
  if (n-x) mod 2 =1 then inc(ans);
  writeln(ans);
end.

水题

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

int a[30010] = {};
const int INF = 100000;

int main()
{
    int w, n, tail, ans = 0;
    scanf("%d%d", &w, &n);
    for(int i = 1;i <= n; i++)
        scanf("%d", &a[i]);
    tail = n;
    sort(a+1, a+1+n);
    for(int i = 1;i <= n; i++)
    {
        if(i > tail)    break;
        if(i == tail)
        {
            ans++;
            break;
        }
        for(int j = tail;j >= 1; j--)
        {
            if(a[i] + a[j] <= w)
            {
                a[j] = INF;
                ans++;
                tail--;
                break;
            }
            else
            {
                ans++;
                tail--;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

ccc试了那么多次，没AC的原因竟然是数组边界少了= =|||
program group;
var
w,n,i,j,l,r,count:longint; a:array [0..100000] of longint;
procedure qsort(head,last:longint);
var i,j,mid,t:longint;
begin
i:=head; j:=last;
mid:=a[(head+last) div 2];
while i<j do
begin
while a[i]<mid do inc(i);
while a[j]>mid do dec(j);
if (i<=j) then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);
dec(j);
end;
end;
if head<j then qsort(head,j);
if last>i then qsort(i,last);
end;
begin
readln(w);
readln(n);
for i:=1 to n do readln(a[i]);
qsort(1,n);
l:=1; r:=n;
while l<=r do
begin
if (a[l]+a[r]<=w) then begin
inc(count);
inc(l);
dec(r);
end
else begin
inc(count);
dec(r);
end;
end;
if l=r then inc(count);
write(count);
end.

program p1409;
var
a:array[1..30000] of longint;
i,n,m,ans,x:longint;
procedure qsort(l,r:longint);
var i,j,mid,p:longint;
begin
i:=l;
j:=r;
mid:=a[(l+r) div 2];
repeat
while a[i]>mid do
i:=i+1;
while a[j]<mid do
j:=j-1;
if i<=j then
begin
p:=a[i];
a[i]:=a[j];
a[j]:=p;
i:=i+1;
j:=j-1;
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
begin
readln(m);
readln(n);
ans:=0;
for i:=1 to n do
readln(a[i]);
qsort(1,n);
i:=1;x:=n;
while i<x do
begin
if a[i]+a[x]<=m then
begin
inc(i);
x:=x-1;
ans:=ans+1;
end
else
begin
i:=i+1;
ans:=ans+1;
end;
if i=x then ans:=ans+1;
end;
write (ans);
end.

-AC60纪念-
测试数据 #0: Accepted, time = 0 ms, mem = 1036 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1040 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1040 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1036 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1036 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1040 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1040 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1040 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1040 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1036 KiB, score = 10
Accepted, time = 15 ms, mem = 1040 KiB, score = 100
```pascal
type int=longint;
var
n,m,i,j,k,tail,head,ans:int;
a,d:array[0..30001]of int;

procedure qsort(l,r:int);
var
i,j,m,p:int;
begin
i:=l; j:=r; m:=a[(l+r) div 2];
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then
begin
p:=a[i];
a[i]:=a[j];
a[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;

begin
readln(n);
readln(m);
ans:=0; k:=0;
for i:=1 to m do readln(a[i]);
qsort(1,m);
head:=1;
tail:=m;
repeat
while a[tail]+a[head]>n do dec(tail);
if head<tail then
begin
inc(k);
d[k]:=tail;
inc(ans);
inc(head);
dec(tail);
end;
until tail<=head;
dec(head); inc(tail);
ans:=ans+d[k]-head-1+m-d[1];
for i:=1 to k-1 do ans:=ans+d[i]-d[i+1]-1;
writeln(ans);
readln;
end.
```

有一道水题，简单贪心
现附代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#define maxn 30005
using namespace std;

int s[maxn];
int main(){
int m,n;
cin>>m>>n;
memset(s,0,sizeof(s));
for(int i=0;i<n;i++)scanf("%d",&s[i]);
sort(s,s+n);
int d=0;
int x=0,y=n-1;
while(x<=y){
if(x==y){
d++;
break;
}else{
if(s[x]+s[y]<=m){d++;x++;y--;}
else {d++;y--;}
}
}

cout<<d<<endl;
return 0;
}

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;

const int maxn = 30000;
int n,v[maxn + 2],w;
bool vis[maxn + 2];

int main(){
scanf("%d%d",&w,&n);
int ans = 0;
memset(vis,0,sizeof(vis));
for(int i = 1;i <= n;i ++){
scanf("%d",&v[i]);
}
sort(v + 1,v + 1 + n);
for(int i = 1;i <= n;i ++){
for(int j = n;j >= i + 1;j --){
if(!vis[i] && !vis[j]){
if(v[i] + v[j] <= w){
vis[i] = 1; vis[j] = 1;
ans ++;
}
}
}
}
ans += n - ans * 2;
printf("%d",ans);

return 0;
}
waterful