「BZOJ2091」The Minima Game

2014年10月20日2,2830

Description

给出N个正整数，AB两个人轮流取数，A先取。每次可以取任意多个数，直到N个数都被取走。
每次获得的得分为取的数中的最小值，A和B的策略都是尽可能使得自己的得分减去对手的得分更大。
在这样的情况下，最终A的得分减去B的得分为多少。

Input

第一行一个正整数N (N <= 1,000,000)，第二行N个正整数（不超过10^9）。

Output

一个正整数，表示最终A与B的分差。

Sample Input

3
1 3 1

Sample Output

HINT

第一次A取走3，第二次B取走两个1，最终分差为2。

题解

排序一下

f[i]表示前i个先手能取到的最大得分差

f[i]=max(f[i-1],a[i]-f[i-1])

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#include<queue>
#define pa pair<int,int>
#define inf 1000000000
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int a[1000005],f[1000005];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    sort(a+1,a+n+1);
    f[1]=a[1];
    for(int i=2;i<=n;i++)
        f[i]=max(f[i-1],a[i]-f[i-1]);
    printf("%d",f[n]);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<set>

#include<queue>

#define pa pair<int,int>

#define inf 1000000000

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int a[1000005],f[1000005];

int main()

{

n=read();

for(int i=1;i<=n;i++)a[i]=read();

sort(a+1,a+n+1);

f[1]=a[1];

for(int i=2;i<=n;i++)

f[i]=max(f[i-1],a[i]-f[i-1]);

printf("%d",f[n]);

return 0;

}

« 「CF480C」Riding in a Lift 「JoyOI1097」MM不哭 »

hzwer.com _ Home | http://hzwer.com

「BZOJ2091」The Minima Game

Description

Input

Output

Sample Input

Sample Output

HINT

分类目录

热门文章

Myfriends

近期评论