题解

229 条题解

  • 0
    @ 2018-06-27 19:48:40

    先排序
    从小枚举到大
    ```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);
    }
    ```

  • 0
    @ 2018-06-11 11:15:46

    #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;
    }

  • 0
    @ 2018-06-01 21:03:30

    贪心,每次 一个可用最大的配上一个可用最小的 ,配不了的单独为一组
    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;
    }
    
  • 0
    @ 2018-05-05 11:00:01

    #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;
    }

  • 0
    @ 2018-05-05 10:59:04

    #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;
    }

  • 0
    @ 2018-04-10 10:38:45
    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;
        }
    }
    
    
  • 0
    @ 2017-10-14 16:33:34

    破题

  • 0
    @ 2016-07-22 15:32:54

    从两头开始枚举,编号分别设为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;

    }
    ```

  • 0
    @ 2016-07-14 15:41:11

    #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;
    }

  • 0
    @ 2016-06-22 13:55:01

    这不是传说中的乘船问题
    #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;
    }

  • 0
    @ 2016-05-21 16:50:10

    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.

  • 0
    @ 2016-05-21 16:40:51

    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.

  • 0
    @ 2016-05-08 11:12:35

    随便写个乱七八糟的贪心竟然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
    @ 2016-04-01 16:38:14

    水到极致
    测试数据 #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.
    
  • 0
    @ 2016-03-24 23:01:44

    水题

    #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;
    }
    
  • 0
    @ 2016-03-20 17:00:50

    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.

  • 0
    @ 2016-03-16 16:31:31

    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.

  • 0
    @ 2016-03-13 21:40:42

    -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.
    ```

  • 0
    @ 2016-03-10 20:05:37

    有一道水题,简单贪心
    现附代码
    #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;
    }

  • 0
    @ 2016-03-02 17:02:02

    #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

信息

ID
1409
难度
4
分类
贪心 点击显示
标签
递交数
8081
已通过
3181
通过率
39%
被复制
25
上传者