chair

Qsort！

/*Tokgo*/
/*
要想分组数少，
只要尽量两个一组
从最贵的开始考虑，
只要剩余最小的能塞进去就塞进去
此决策一定是最优的。
(设a>b>c>d,若a+d<w则b+c<w)
不断这样决策就能得到最优解了。
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int a[30001];
int ans;
int p=1;
int main()
{
    int n,w;
    cin>>w>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=n;i>=1;--i){
        if(p>i) break;
        ++ans;
        if(w>=a[p]+a[i])
            ++p;
    }
    cout<<ans;
    return 0;
}

#include <stdio.h>
#include <algorithm>
using namespace std;
int w, n;
int a[30010];
int v[30010];
int main()
{
scanf( "%d%d", &w, &n );
for ( int i = 0 ; i < n ; ++ i )
{
scanf( "%d", &a[i] );
}
sort( a, a+n );
int cnt = 0;
for ( int i = n-1 ; i >= 0 ; -- i )
{
if ( v[i] ) continue;
v[i] = true;
for ( int j = i-1 ; j >= 0 ; -- j )
{
if ( !v[j] && a[i] + a[j] <= w )
{
v[j] = true;
break;
}
}
cnt ++;
}
printf( "%d", cnt );
return 0;
}

排序，双向逼近。
#include <iostream>
#include <algorithm>
using namespace std;

int w,n;
int arr[30005];
int number=0;

int main() {
cin>>w>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
sort(arr+0,arr+n);
int x=0,y=n-1;
while(x<=y){
if((arr[x]+arr[y])<=w){
x++;y--;number++;
}else{
y--;number++;
}
}
cout<<number;
return 0;
}

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.

秒过，水题
Const
inf = 'group.in';
ouf = 'group.out';
Var
a: Array[1..30000]Of Longint;
max, n, i, j, k: Longint;
Procedure sort(l, r: Longint);
Var
i, j, x, t: Longint;
Begin
i := l; j := r;
x := a[(i + j) Div 2];
Repeat
While a[i] < x Do Inc(i);
While a[j] > x Do Dec(j);
If i <= j Then Begin
t := a[i]; a[i] := a[j]; a[j] := t;
Inc(i); dec(j);
End;
Until i > j;
If i < r Then sort(i, r);
If l < j Then sort(l, j);
End;
Begin
Assign(input, inf); Reset(input);
Assign(output, ouF); Rewrite(output);
Readln(max);
ReadLn(n);
For i:=1 To n Do ReadLn(a[i]);
sort(1, n);
If n = 1 Then Begin
Writeln('1');
Close(output);
Halt;
End;
i := 1; j := n; k := 0;
Repeat
If a[j] + a[i] <= max Then Begin
Inc(k); Dec(j); Inc(i);
End Else Begin
Inc(k);
Dec(j);
End;
Until i > j;
Writeln(k);
Close(input); Close(output);
End.

问题何在？
* * Wrong Answer
/usr/bin/ld.bfd: warning: /out/link.res contains output sections; did you forget -T?

状态 耗时 内存占用

#1 Accepted 1ms 256.0KiB
#2 Accepted 0ms 256.0KiB
#3 Accepted 1ms 256.0KiB
#4 Accepted 1ms 256.0KiB
#5 Accepted 1ms 256.0KiB
#6 Wrong Answer 81ms 256.0KiB
#7 Accepted 427ms 256.0KiB
#8 Accepted 449ms 256.0KiB
#9 Wrong Answer 823ms 340.0KiB
#10 Wrong Answer 955ms 256.0KiB
代码
var
w,n,i,j,k,t:longint;
a,b:array[1..30000]of integer;
f:boolean;
begin
readln(w);readln(n);for i:=1 to n do readln(a[i]);
for i:=1 to n-1 do begin
k:=i;
for j:=i+1 to n do
if a[k]<a[j] then k:=j;
if k<>i then begin
t:=a[k];a[k]:=a[i];a[i]:=t;
end;
end;
b[1]:=a[1];j:=1;
for i:=2 to n do begin
f:=false;
for k:=1 to j do if b[k]+a[i]<=w then begin inc(b[k],a[i]);f:=true;break;end;
if f=false then begin inc(j);inc(b[j],a[i]);end;
end;
writeln(j);
end.*

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

int awards[30005];

int main() {
    int w,n;
    cin >> w >> n;
    for(int i = 0; i < n; i++) {
        cin >> awards[i];
    }
    sort(awards,awards+n);
    int ptrLeft = 0;
    int ptrRight = n - 1;
    int numGroup = n;
    while(ptrLeft < ptrRight) {
        if(awards[ptrLeft] + awards[ptrRight] <= w) {
            numGroup--;
            ptrLeft++;
            ptrRight--;
        } else {
            ptrRight--;
        }
    }
    cout << numGroup << endl;
    return 0;
}

写了两种解法 一种从大到小 一种从小到大 从小到大真的麻烦。。。各种小问题
从大到小：

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int w, n;
    cin >> w >> n;
    int obj[n];
    for (int i = 0; i < n; i++){
        cin >> obj[i];
    }
    sort(obj, obj + n);
    int left = 0, right = n - 1;
    int objCount = 0;
    int count = 0;
    while (objCount < n){
        if (obj[right] + obj[left] <= w) objCount += 2, right--, left++;
        else right--, objCount++;
        count++;
    }
    cout << count << endl;
}

从小到大：

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

bool helper(int a, int b){
    return a < b;
}

int main(){
    int w, n, count = 0;
    cin >> w >> n;
    int obj[n];
    
    for (int i = 0; i < n; i++){
        cin >> obj[i];
    }
    sort(obj, obj + n, helper);
    for (int i = 0; i < n; i++) {
        if (obj[i] != -1){
            count++;
            for (int j = i + 1; j < n; j++){
                if (obj[i] + obj[j] > w|| obj[j] == -1){
                    obj[j - 1] = -1;
                    break;
                }
                else if (j == n - 1) obj[n - 1] = -1;
            }
            obj[i] = -1;
        }
    }
    cout << count << endl;
    return 0;
    
}

#include<stdio.h>
#include<stdlib.h>
int compare(const void *value1, const void *value2);
int main()
{
    int w, n, g[30000], i, j, count = 0;
    scanf("%d%d", &w, &n);
    for (i = 0; i < n; i++)
        scanf("%d", &g[i]);     
    qsort(g, n, sizeof(int), compare);
        for (i = 0, j = n - 1; j >= i; j--)    //分别从第一个元素和最后一个元素相加进行判断
        {
            if (g[i] + g[j] > w)
                count++;
            else {
                count++;
                i++;
            }
        }
    printf("%d", count);
    return 0;
}
int compare(const void *value1, const void *value2)
{
    return *(int*)value1 - *(int*)value2;
}

#include "iostream"
#include "algorithm"
using namespace std;
int main()
{
int a[30000],n,w;
int i,j = 1;
scanf("%d%d",&w,&n);
for (int r = 0; r < n; r++)
scanf("%d",&a[r]);
sort(a,a+n);

int mem = n;
for(i = 0,j; i < n && i != j; )
{
for(j = mem-1;j > i; j--)
if(a[i] + a[j] <= w)
{
a[j] = a[j] +a[i];
a[i] = -1;
i++;
mem = j;
break;
}
}
printf("%d",n-i);
return 0;
}

简单贪心，练手一下deque

#include <deque>
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int a[30010];

int main()
{
    int w,n;
    cin >> w >> n;
    for (int i = 0; i < n; i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a,a+n);
    deque <int> s(a,a+n);
    int ans = 0;
    while (s.begin()!=s.end())
    {
        ans++;
        if (s.size() <= 1) break;
        int a = s.front(), b = s.back();
        
        if (a + b <= w)
        {
            s.pop_front();
        }
        s.pop_back();   
    }
    cout << ans << endl;
}

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n,m;
    int num[30001]={0};
    cin >> m >> n;
    for (int i=0;i<n;i++) cin >> num[i];
    sort(num,num+n);
    int i=0; int j=n-1;
    int sum=0;
    while (j>=i)
    {
        if (num[j]+num[i]<=m)
        {
            j--; i++;
        }
        else j--;
        sum++;
    }
    cout << sum;
}

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
int w,g,a[30005],i,m,n,an;
int main()
{
cin>>w>>g;
for(i=0;i<g;i++) cin>>a[i];
sort(a,a+g);m=0;n=g-1;
while(n>=m)
{
if(a[m]+a[n]<=w)
{
m++;
n--;
}
else
{
n--;
}
an++;
}
cout<<an<<endl;
system("pause");
return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int N,max_num,times=0; 
int val[30020];
void sort(int lb,int ub){
    if(lb>=ub){
        return;
    }
    int m = lb;
    for(int i = lb+1; i <= ub ;i++){
        if(val[i]<val[lb]){
            m++;
            swap(val[i],val[m]);            
        }
    }
    swap(val[lb],val[m]);
    sort(lb,m-1);
    sort(m+1,ub);
}
int main(){
    cin>>max_num>>N;
    int low=1,up=N;
    for(int i = 1; i <= N ; i++){
        cin>>val[i];
    }
    sort(1,N);
    while(low<=up){
        if((val[low]+val[up])<=max_num){
            low++;
            up--;
            times++;
        }else{
            up--;
            times++;
        }
    }
    cout<<times<<endl;
    return 0;   
} 

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 624 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 624 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 624 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 624 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 632 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 628 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 624 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 624 KiB, score = 10
Accepted, time = 30 ms, mem = 632 KiB, score = 100
代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int l,r,w,n,a[30030],num;

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

只要排序，从首尾贪心找即可

#include <iostream>
#include <cmath>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <climits>  
#include <algorithm>
#include <set>
#include <vector>

using namespace std;


int main()
{
  int m,n;
  cin>>m>>n;

  int sum=0;

  int x;

  vector<int> ss;
  vector<int>::iterator i;
  vector<int>::iterator j; 

  for(int i=1;i<=n;i++)
    {
      cin>>x;
      ss.push_back(x);
    }

  sort(ss.begin(),ss.end());

  j=ss.begin();
  for(i=ss.end()-1; i>=ss.begin(),i>=j; i--)
  { 
    if(i==j){sum++;}
    else
    {
      if(*i+*j <= m){j++;sum++;}
      else{sum++;}
    }   
  }

  cout<<sum;

  return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=30005;
int price[N];
int main()
{
    int w,n,ans(0);
    scanf("%d%d",&w,&n);
    for(int i=0;i<n;i++)scanf("%d",&price[i]);
    sort(price,price+n);
    int low=0,high=n-1;
    while(low<high)
        if(price[low]+price[high]<=w) ans++,low++,high--;
        else ans++,high--;
    if(low==high) ans++;
    printf("%d\n",ans);
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int maxnum,n;
vector <int> lpo;

void ksortlpo(int l,int r)
{
int mid=lpo[(l+r)/2];
int i=l,j=r;
do
{
while(lpo[i]<mid)++i;
while(mid<lpo[j])--j;
if(i<=j)
{
swap(lpo[i],lpo[j]);
++i;
--j;
}
}while(i<=j);
if(i<=r)ksortlpo(i,r);
if(j>=l)ksortlpo(l,j);
return;
}

int main()
{
int i ,j;
int ans=0;
cin>>maxnum>>n;
lpo.resize(n);
for(i=0;i<n;++i)
cin>>lpo[i];
ksortlpo(0,n-1);//排序
for(i=0,j=n-1;i<=j;)//贪心
{
if(lpo[i]+lpo[j]<=maxnum)
{
ans++;
i++;
j--;
}else
{
ans++;
j--;
}
}
cout<<ans;

return 0;
}

var a:array[0..10000]of longint;
w,n,i,l,r,ans: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);
readln(n);
for i:=1 to n do
readln(a[i]);
sort(1,n);
l:=1; r:=n; ans:=n; //假设需要N个盒子
while l<r do
begin
if a[l]+a[r]<=w then //如果方案合法,答案减一,左端点右移一位
begin
dec(ans);
inc(l);

end;
dec(r); //不论是否合法,右端点左移一位
end;
writeln(ans);
end.