题解

229 条题解

  • 0
    @ 2015-11-03 22:11:32

    SO EASY
    var
    w,n,i,j,ans:longint;
    a:array[1..50000]of 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
    read(w,n);for i:=1 to n do read(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;
    ans:=ans+1;
    end
    else
    begin
    j:=j-1;
    ans:=ans+1;
    end;
    end;
    write(ans);
    end.

  • 0
    @ 2015-08-28 15:52:28

    program qs;
    var
    p,n,b,c,s,w:longint;
    a:array[1..30005]of longint;
    procedure qs(l,r:longint);
    var
    i,j,m,t:longint;
    begin
    i:=l;j:=r;m:=a[l];
    repeat
    while a[i]<m do inc(i);
    while a[j]>m 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 l<j then qs(l,j);
    if i<r then qs(i,r);
    end;
    begin
    c:=0;
    readln(w,n);
    for p:=1 to n do
    read(a[p]);
    qs(1,n);
    b:=n;s:=1;
    while s<=b do
    begin
    if a[s]+a[b]<=w then
    begin
    c:=c+1;dec(b);inc(s);
    end
    else
    begin
    c:=c+1;dec(b);
    end;
    end;
    write(c);
    end.

  • 0
    @ 2015-08-26 20:51:23

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <functional>
    using namespace std;
    const int maxn=30005;
    int main()
    {
    int maxWeight,count;
    int weight[maxn];
    scanf("%d%d",&maxWeight,&count);
    for(int i=0;i<count;i++) scanf("%d",&weight[i]);
    sort(weight,weight+count,greater<int>());

    int head=0,tail=count-1;
    int ans=0;
    while(head<tail) {
    if(weight[head]+weight[tail]<=maxWeight) tail--;
    head++;
    ans++;
    }
    if(head==tail) ans++;
    printf("%d",ans);
    return 0;
    }

  • 0
    @ 2014-12-10 15:24:20

    var i,j,v,n,m,k,s,t:longint;
    a:array[1..100]of longint;
    procedure q(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;
    inc(i);dec(j);
    end;
    until i>j;
    if l<j then q(l,j);
    if i<r then q(i,r);
    end;
    begin
    readln(m,n);
    for i:=1 to n do readln(a[i]); s:=0;
    q(1,n);
    v:=1;
    k:=n;
    while n>0 do
    begin
    if a[v]+a[k]<=100 then begin s:=s+1;v:=v+1;k:=k-1;n:=n-2;end
    else begin s:=s+1;k:=k-1;n:=n-1;end;
    end;
    writeln(s);
    end.

  • 0
    @ 2014-11-06 16:12:28

    var
    w,n,i,m,j:integer;
    p:array[0..30000] of integer;
    procedure qsort(l,r:integer);
    var
    i,j,k,x:integer;
    begin
    k:=random(r-l+1)+l;
    x:=p[k];
    i:=l;
    j:=r;
    repeat
    while p[i]<x do i:=i+1;
    while p[j]>x do j:=j-1;
    if i<=j then
    begin
    p[0]:=p[i];
    p[i]:=p[j];
    p[j]:=p[0];
    i:=i+1;
    j:=j-1;
    end;
    until i>j;
    if i<r then qsort(i,r);
    if j>l then qsort(l,j);
    end;
    begin
    readln(w);
    readln(n);
    for i:=1 to n do
    readln(p[i]);
    qsort(1,n);
    i:=0;
    m:=n;
    j:=1;
    repeat
    if p[m]+p[j]<=w then
    begin
    i:=i+1;
    m:=m-1;
    j:=j+1;
    end
    else
    begin
    i:=i+1;
    m:=m-1;
    end;
    until m<j;
    writeln(i);
    end.

  • 0
    @ 2014-11-02 20:45:34

    测试数据 #0: Accepted, time = 0 ms, mem = 932 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 932 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 932 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 928 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 932 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 932 KiB, score = 10
    测试数据 #6: Accepted, time = 15 ms, mem = 932 KiB, score = 10
    测试数据 #7: Accepted, time = 15 ms, mem = 932 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 932 KiB, score = 10
    测试数据 #9: Accepted, time = 0 ms, mem = 928 KiB, score = 10
    Accepted, time = 45 ms, mem = 932 KiB, score = 100
    快排 水题一道

  • 0
    @ 2014-11-01 16:13:53

    快排+大小比对
    var a:array[1..30000] of longint;
    w,n,i,j,t:longint;
    procedure kp(l,r:longint);
    var i,j,mid,t:longint;
    begin
    i:=l;j:=r;
    mid:=a[(i+j) div 2];
    repeat
    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;
    until i>j;
    if i<r then kp(i,r);
    if l<j then kp(l,j);
    end;
    begin
    read(w);
    read(n);
    for i:=1 to n do
    read(a[i]);
    kp(1,n);
    i:=1;j:=n;
    while i<=j do
    begin
    if a[i]+a[j]<=w then begin inc(i);dec(j);end
    else dec(j);
    inc(t);
    end;
    write(t);
    end.

    测试数据 #0: Accepted, time = 15 ms, mem = 848 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 848 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 844 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 848 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 844 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 848 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 840 KiB, score = 10
    测试数据 #7: Accepted, time = 31 ms, mem = 844 KiB, score = 10
    测试数据 #8: Accepted, time = 15 ms, mem = 844 KiB, score = 10
    测试数据 #9: Accepted, time = 15 ms, mem = 844 KiB, score = 10
    Accepted, time = 76 ms, mem = 848 KiB, score = 100

  • 0
    @ 2014-10-31 19:42:31

    一次AC,考虑了多种情况,通过即可

    贪心的方法是:先快排,从大到小,然后选从最大到最小,尽量使2个物品和接近W,然后标记为不可选取,答案+1,继续选取。

    program ex;
    var data:array[0..30001] of longint;
    a,b,c,w,i,j,num,n,ans:longint;

    procedure qsort(x,y:longint);
    var i,r,mid,l,j,k:longint;
    begin
    r:=x; l:=y;
    mid:=data[(x+y) div 2];

    repeat
    while data[r]>mid do inc(r);
    while data[l]<mid do dec(l);

    if r<=l then
    begin
    k:=data[r];
    data[r]:=data[l];
    data[l]:=k;
    inc(r);
    dec(l);
    end;
    until r>l;

    if x<l then qsort(x,l);
    if r<y then qsort(r,y);

    end;

    begin //main
    ans:=0;
    read(w); read(n);
    data[n+1]:=201;
    for i:=1 to n do
    begin
    read(num);
    data[i]:=num;
    end;

    qsort(1,n);

    for i:=1 to n do
    begin
    a:=data[i];

    if data[i]=201 then
    continue;
    if data[i]>w then
    begin
    data[i]:=201;
    continue;
    end;

    for j:=i+1 to n+1 do
    begin
    if (a+data[j])<=w then
    begin
    a:=0;
    data[j]:=201;
    data[i]:=201;
    ans:=ans+1;
    break;
    end;
    if j=n+1 then
    begin
    a:=0;
    data[i]:=201;
    ans:=ans+1;
    end;

    end;
    end;
    write(ans);
    end.

    • @ 2014-10-31 19:48:10

      虽然可能题目没说,写的时候为了1次AC考虑了所有情况

      第一种是普通情况,测试数据代入即可

      第二种是都给你5 5 5 5 5价值的东西,可能程序不完善,没有2个2个放一起

      第三种可能给你超过W价值的东西,要排除掉;

      以上三种类型数据都能过,基本秒AC

    • @ 2014-10-31 19:49:49

      我这个可能最后一个数据要超时- -自己优化一下吧(如果电脑卡的话)

    • @ 2014-10-31 19:57:24

      可能用boolean判断可以省时间,懒得搞了- -

    • @ 2014-10-31 19:58:38

      好吧,是能省一倍的时间= =

  • 0
    @ 2014-10-30 23:15:06

    5min水过。
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int pi[30001];
    int main()
    {
    int w,n;
    cin>>w>>n;
    for(int i=0;i<n;i++)
    cin>>pi[i];
    sort(pi,pi+n);
    int count=0,ans=0;
    for(int i=n-1;i>=0;i--)
    {
    int flag=1;
    for(int j=count;j<i;j++)
    {
    if(pi[i]+pi[j]<=w)
    {
    ans++;
    count++;
    flag=0;
    break;
    }
    }
    if(flag)
    {
    ans++;
    }
    if(i==count)
    break;
    }
    cout<<ans<<endl;
    return 0;
    }
    排序之后大小配对。

  • 0
    @ 2014-10-26 20:02:53

    var
    flag:boolean;
    bool:array[1..100000] of boolean;
    w,i,j,n,k,temp,tot:longint;
    a:array[1..30000] of longint;
    procedure qsort(l,r:longint);
    var
    i,j,k:longint;
    begin
    i:=l;
    j:=r;
    k:=(i+j) div 2;
    temp:=a[k];
    a[k]:=a[l];
    while i<j do
    begin
    while (i<j)and(a[j]>temp) do
    dec(j);
    if i<j then
    begin
    a[i]:=a[j];
    inc(i);
    end;
    while (i<j)and(a[i]<temp) do
    inc(i);
    if i<j then
    begin
    a[j]:=a[i];
    dec(j);
    end;
    end;
    a[i]:=temp;
    if i-1>l then
    qsort(l,i-1);
    if i+1<r then
    qsort(i+1,r);
    end;

    begin
    readln(w);
    readln(n);
    for i:=1 to n do
    readln(a[i]);
    qsort(1,n);

    for i:=1 to n do
    if not bool[i] then
    begin
    flag:=false;
    for j:=n downto i+1 do
    if (not bool[j])and(a[i]+a[j]<=w) then
    begin
    bool[i]:=true;
    bool[j]:=true;
    flag:=true;
    inc(tot);
    break;
    end;
    if not flag then
    break;
    end;
    writeln(n-tot);
    end.
    关于淳朴的贪心

  • 0
    @ 2014-08-25 22:02:12

    var
    a:array[1..200]of longint;
    c,w,n,b,i,j,ans:longint;
    begin
    readln(w);readln(n);for i:=1 to n do begin readln(b);inc(a[b]);end;
    for i:=1 to w do
    begin
    c:=0;
    while (a[i]>0)and(a[i]<>c) do
    begin
    c:=a[i];
    for j:=w downto i+1 do while (a[i]>0)and(a[j]>0)and(i+j<=w)do
    begin dec(a[i]);dec(a[j]);inc(ans);end;
    end;
    end;
    for i:=1 to w do while (2*i<=w)and(a[i]>=2) do begin dec(a[i],2);inc(ans);end;
    writeln(n-ans);
    end.

  • 0
    @ 2014-08-09 00:56:09

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

    int main()
    {
    int pi[300000], w, n, sum = 0, i, j;
    cin >> w;
    cin >> n;
    for(i = 0; i < n; i++) cin >> pi[i];
    sort(pi, pi + n);
    for(i = 0, j = n - 1; i <= j;) {
    if(pi[i] + pi[j] <= w) {
    sum++;

    i++;
    } else if(pi[j] <= w) {
    sum++;
    }
    j--;
    }
    if(i == j) sum++;
    cout << sum << "\n";

    return 0;
    }

    这是我源码

    评测结果

    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 1416 KiB, score = 10

    测试数据 #1: Accepted, time = 0 ms, mem = 1412 KiB, score = 10

    测试数据 #2: Accepted, time = 0 ms, mem = 1416 KiB, score = 10

    测试数据 #3: Accepted, time = 0 ms, mem = 1412 KiB, score = 10

    测试数据 #4: Accepted, time = 0 ms, mem = 1416 KiB, score = 10

    测试数据 #5: Accepted, time = 46 ms, mem = 1416 KiB, score = 10

    测试数据 #6: Accepted, time = 93 ms, mem = 1416 KiB, score = 10

    测试数据 #7: Accepted, time = 78 ms, mem = 1412 KiB, score = 10

    测试数据 #8: Accepted, time = 93 ms, mem = 1416 KiB, score = 10

    测试数据 #9: Accepted, time = 124 ms, mem = 1412 KiB, score = 10

    Accepted, time = 434 ms, mem = 1416 KiB, score = 100

    运行都对了,但是在soj上却通过不了,是因为vijos的测试数据没有soj好吗,soj是1483题,哪位大神能说明下呢

  • 0
    @ 2014-04-22 20:51:31

    整理一下,刚才发的不好。
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int a[1000001];
    int main()
    {
    int w,n,i,k=0,l,js=0;
    cin>>w>>n;
    for(i=0;i<=n-1;i++)cin>>a[i];
    int j=n-1;
    sort(a,a+n);
    while(j>=k)
    {
    while(a[j--]+a[k]>w)js++;
    js++,k++;
    }
    cout<<js<<endl;
    return 0;
    }

  • 0
    @ 2014-04-22 20:49:36

    超短20行版!!!
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int a[1000001];
    int main()
    {
    int w,n,i,k=0,l,js=0;
    cin>>w>>n;
    for(i=0;i<=n-1;i++)cin>>a[i];
    int j=n-1;
    sort(a,a+n);
    while(j>=k)
    {
    while(a[j--]+a[k]>w)js++;
    js++,k++;
    }
    cout<<js<<endl;
    return 0;
    }

  • 0
    @ 2014-01-21 17:36:47

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n,m;
    int a[30005];
    int ans;
    int main()
    {
    cin>>n;
    cin>>m;
    for(int i=1;i<=m;i++)cin>>a[i];
    sort(a+1,a+m+1);
    int x=1;int y=m;
    while(x!=y)
    {
    if(a[x]+a[y]>n)
    {
    ans++;
    y--;
    }
    else
    {
    x++;y--;ans++;
    }
    if(x==y){
    ans++;break;
    }
    if(x>y)break;
    }
    cout<<ans<<endl;
    return 0;
    }

  • 0
    @ 2013-11-09 11:32:51

    为什么会超时?????????????????????
    BS!!!!!!!!!!!!!!!!!!!

    var
    gift:array[1..30000] of integer;
    maxn,n,i,j,t,s,flag:integer;
    begin
    readln(maxn);
    readln(n);
    for i:=1 to n do readln(gift[i]);
    for i:=1 to n-1 do
    for j:=i+1 to n do
    if gift[i]<gift[j] then
    begin
    t:=gift[i];gift[i]:=gift[j];gift[j]:=t;
    end;
    for i:=n downto 1 do
    begin
    flag:=0;
    for j:=1 to i-1 do
    if (gift[i]+gift[j]<=maxn) and (gift[i]<>-1) and (gift[j]<>-1) then
    begin
    s:=s+1;
    gift[i]:=-1;
    gift[j]:=-1;
    flag:=1;
    break;
    end;
    if (flag=0) and (gift[i]<>-1) then s:=s+1;
    end;
    writeln(s);
    end.

  • 0
    @ 2013-10-31 22:11:31

    这道题建议用基数排序,速度最快,时间复杂度最低
    评测结果
    编译成功

    foo.pas(18,11) Warning: Variable "p" does not seem to be initialized
    foo.pas(49,17) Warning: Variable "ans" does not seem to be initialized
    测试数据 #0: Accepted, time = 15 ms, mem = 940 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 944 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 944 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 940 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 944 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 944 KiB, score = 10
    测试数据 #6: Accepted, time = 140 ms, mem = 944 KiB, score = 10
    测试数据 #7: Accepted, time = 140 ms, mem = 944 KiB, score = 10
    测试数据 #8: Accepted, time = 296 ms, mem = 944 KiB, score = 10
    测试数据 #9: Accepted, time = 359 ms, mem = 940 KiB, score = 10
    Accepted, time = 965 ms, mem = 944 KiB, score = 100

    程序:
    program present;
    var w,n,i,j,t,ans,tt:longint;
    a:array[0..30000] of longint;
    p:array[1..200] of longint;
    sweep:boolean;
    begin
    //assign(input,'present.txt');
    //reset(input);
    read(w,n);
    for i:=1 to n do
    read(a[i]);
    //close(input);
    //assign(input,'');
    //reset(input);
    tt:=1;
    a[0]:=1000;
    for i:=1 to n do
    inc(p[a[i]]);
    for i:=200 downto 1 do
    if p[i]>0 then
    begin
    for j:=tt to tt+p[i]-1 do
    a[j]:=i;
    tt:=tt+p[i];
    end;
    for i:=1 to n do
    begin
    j:=n;
    tt:=0;
    if a[i]=0 then
    continue;
    while (a[j]=0) and (j>0) do dec(j);
    while a[i]+a[j]<=w do
    begin
    if i>=j then
    break;
    if (a[tt]<>a[j]) and (j>0) then
    tt:=j;
    dec(j);
    while (a[j]=0) and (j>0) do dec(j);
    if j=0 then
    break;
    end;
    j:=tt;
    if j=0 then
    j:=i;
    if a[i]<>0 then
    begin
    inc(ans);
    a[i]:=0;
    a[j]:=0;
    end;
    end;
    writeln(ans);
    //readln(ans);
    end.

  • 0
    @ 2013-10-19 09:50:43

    include <cstdlib> include <iostream>

    using namespace std;

    int main(int argc, char *argv[])
    {
    int m,s,t,dis,time;
    time=0;
    dis=0;
    cin>>m>>s>>t;
    while (1)
    {
    if (dis>=s)
    {
    cout<<"Yes"<<endl;
    cout<<time;
    break;
    }
    else
    {
    if (time<t)
    {
    if (m>=10)
    {
    m-=10;
    time+=1;
    dis+=60;
    }
    else
    {
    if ((s-dis)>=60 and (t-time)>=((10-m)-(10-m)%4)/4+1+1)
    {
    m+=4;
    time++;
    }
    else
    {
    time++;
    dis+=17;
    }
    }
    }
    else
    {
    cout<<"No"<<endl;
    cout<<dis;
    }
    }
    }

    return EXIT_SUCCESS;
    }

  • 0
    @ 2013-08-13 16:16:08

    o( ̄▽ ̄)o 刚才没发现 AC40题纪念!~~~~~

  • 0
    @ 2013-08-13 16:15:02

    =、= RP不好 WA了三次。。。 原因是代码复制错了--||
    Var w,n,i,j,ans,t,tmp,head,tail:longint;
    v:array[1..100000] of boolean;
    a:array[1..100000] of longint;
    Procedure qsort(l,r:longint);
    Var i,j,x,y:longint;
    Begin
    i:=l; j:=r;
    x:=a[(l+r) shr 1];
    repeat
    while x>a[i] do inc(i);
    while x<a[j] do dec(j);
    if i<=j then
    begin
    y:=a[i];
    a[i]:=a[j];
    a[j]:=y;
    inc(i); dec(j);
    end;
    Until i>j;
    If i<r then qsort(i,r);
    if l<j then qsort(l,j);
    End;
    Begin
    readln(w);
    readln(n);
    For i:=1 to n do readln(a[i]);
    qsort(1,n);
    head:=1; tail:=n;
    While head<=tail do
    Begin
    tmp:=a[head]+a[tail];
    If tmp<=w then begin inc(ans); inc(head); dec(tail); end;
    If tmp>w then
    Begin
    dec(tail);
    inc(ans);
    End;
    End;
    Writeln(ans);
    End.

信息

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