2015
07-16

Alice and Bob

These days, Alice came up with a new game. In this game, there are some balls placed in a line which are numbered from L to R from left to right. It is known that N of the balls are white, while others are black. Alice will select aCount consecutive balls, after that, Bob will remove bCount balls from the balls that Alice has selected. Bob could remove those bCount balls one by one, for each ball he removes, he can choose whether to select the left most one or right most one.
The goal of Alice is to maximize the number of white balls after Bob’s operation, and Bob’s goal is to minimize this number.
So, what is the maximum number of white balls after Bob’s operation?

There are multiple test cases, for each case:
The first line is an integer N. (1 <= N <= 100,000)
The second line contains two integers L, R. (0 <= L <= R <= 263 – 1)
The third line contains two integers aCount, bCount.
The fourth line contains N integers p[0], p[1], …, p[N - 1], denoting the positions of the white balls.
It is guaranteed that p[i - 1] < p[i] (1 <= i <= N – 1), L <= p[0], p[N - 1] <= R, 0 <= aCount <= R – L + 1, 0<=bCount <= aCount.

There are multiple test cases, for each case:
The first line is an integer N. (1 <= N <= 100,000)
The second line contains two integers L, R. (0 <= L <= R <= 263 – 1)
The third line contains two integers aCount, bCount.
The fourth line contains N integers p[0], p[1], …, p[N - 1], denoting the positions of the white balls.
It is guaranteed that p[i - 1] < p[i] (1 <= i <= N – 1), L <= p[0], p[N - 1] <= R, 0 <= aCount <= R – L + 1, 0<=bCount <= aCount.

2
5 9
3 1
5 8
3
6 10
5 0
6 8 10

1
3

1 母球没有打到任何球，对手+目标球的分数

2 母球没有落袋，但是母球第一次撞击没有撞到目标球，或者是第一次撞击同时撞击了1个以上的球，对手+第一次同时撞击到的球中编号最大的分数

3 母球落袋并且撞击到了至少一个球，对手+第一次同时撞击到的球中编号最大的分数

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int s[10000],hash[200000];
int hit[10000],in[10000];
int a[2],i,j,pot,l_hit,l_in,n,m,flag,flag_pot;

void set()
{
for(int k=0; k<l_in; k++)
hash[in[k]]=1;
while(hash[s[pot]])
pot++;
flag=1-flag;
}

void solve()
{
int sum=0;
for(int k=0; k<l_in; k++)
sum+=in[k];
if(l_hit==0) //没击中球
{
a[1-flag]+=s[pot];
}
else if(in[0]==0&&l_in!=0) //先判断是否有球入袋
{
a[1-flag]+=hit[l_hit-1];
}
else if(l_hit>1||(l_hit==1&&hit[0]!=s[pot])) //过多或不是目标球
{
a[1-flag]+=hit[l_hit-1];
}
else //无犯规
{
if(flag_pot) //目标球进了
{
a[flag]+=sum;
flag=1-flag;
return;
}
}
if(in==0) return;
a[1-flag]+=sum;
}

int main()
{
while(~scanf("%d%d",&n,&m))
{
a[1] = a[0] = 0;
for(i = 1; i<=n; i++)
scanf("%d",&s[i]);
sort(s+1,s+n+1);
memset(hash,0,sizeof(hash));
flag = 0;
pot = 1;
for(i = 0; i<m; i++)
{
flag_pot = 0;
scanf("%d",&l_hit);
for(j = 0; j<l_hit; j++)
scanf("%d",&hit[j]);
scanf("%d",&l_in);
for(j = 0; j<l_in; j++)
{
scanf("%d",&in[j]);
if(in[j] == s[pot])
flag_pot = 1;
}
sort(hit,hit+l_hit);
sort(in,in+l_in);
solve();
set();
}
printf("%d : %d\n",a[0],a[1]);
}

return 0;
}