2013-team5/andrew/13/B

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[2014];

int main(){
    freopen("bandits.in","r",stdin);
    freopen("bandits.out","w",stdout);
    scanf("%d%d",&n,&m);
    a[1]=m; a[2]=-1;
    int i,j,k;
    for (i=3; i<=n; i++){
        sort(a+1,a+i);
        int sum=0,v=i/2+1;
        for (int j=1; j<v; j++) sum+=a[j];
        sum+=v-1;
        if (sum>m){ a[i]=-1; continue; }
        k=v;
        while (k>1 && a[k-1]==a[k]) k--;
        for (j=k; j<i; j++) a[j]=0;
        for (j=1; j<k; j++) a[j]++;
        a[i]=min(m,m-sum);
    }
    printf("%d\n",a[n]);
    return 0;
}

}}}

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,a[2014];
int main(){
    freopen("bandits.in","r",stdin);
    freopen("bandits.out","w",stdout);
    scanf("%d%d",&n,&m);
    a[1]=m; a[2]=-1;
    int i,j,k;
    for (i=3; i<=n; i++){
        sort(a+1,a+i);
        int sum=0,v=i/2+1;
        for (int j=1; j<v; j++) sum+=a[j];
        sum+=v-1;
        if (sum>m){ a[i]=-1; continue; }
        k=v;
        while (k>1 && a[k-1]==a[k]) k--;
        for (j=k; j<i; j++) a[j]=0;
        for (j=1; j<k; j++) a[j]++;
        a[i]=min(m,m-sum);
    }
    printf("%d\n",a[n]);
    return 0;
}