给出一个长度为
N
N
N的序列,两人轮流取数,每次只能取上一次取的数旁边相邻的数,如果没有则任意,两人都尽可能使自己取数总和大,求最后两人取的数总和分别是多少。
N
≤
300000
N≤300000
N≤300000
题解
分析一下取数的过程可以发现,每次
A
A
A取了一个数,
B
B
B取了与之相邻的一个数,限定了一个方向之后,就只能取到最边界才停下,接着下一个人可以任意取,以此类推。
然而知道这就能怎么样呢?
还需要发现其他结论,如果
A
A
A取的数左/右有偶数个数,那么
B
B
B往那个方向去取,取到边界后下一步轮到
B
B
B,则
B
B
B获得先手权,而此时前面已经选择的结果相当于
A
A
A直接从边界开始选,所以此时
A
A
A从中间选不会优于从边界开始选,
也就是说,只有
A
A
A取的数两边个数都是奇数,才会这么选择,否则可以直接从边界选,
于是显然,
N
N
N是偶数时,上述情况无法成立,
A
A
A只能从边界开始,要么从左到右取完所有奇数位置的数,要么从右往左取完所有偶数位置的数,
那么当
N
N
N是奇数怎么办呢?
发现整个过程可以是
A
A
A取偶数位置,
A
A
A和
B
B
B轮流取完某一侧,然后另一侧剩下的数再重复类似的过程,直到某次
A
A
A不取偶数位置,而是把从边界开始(左右开始都一样)把奇数位置取完。
假设最后剩下的区间是
[
l
,
r
]
[l,r]
[l,r],那么
A
A
A在
[
1
,
l
)
[1,l)
[1,l)和
(
r
,
n
]
(r,n]
(r,n]选了所有偶数,
[
l
,
r
]
[l,r]
[l,r]选了所有奇数,那么考虑假设先全选了偶数,然后再反转了一个区间的最大值,也就是找出某个区间中奇数和减去偶数和
S
S
S最大
当然要保证
A
A
A选择的其他偶数起始点断开的区间中的奇数和减偶数和都大于等于
S
S
S,不然
B
B
B会使得
A
A
A选不到最大的
S
S
S,
(盗张图,大概就是这样)
所以说,要找某种断开方式,所有区间最小的奇数和偶数和最大,
自然可以二分答案,然后再判断是否可行,可以用特殊处理的前缀和然后
O
(
n
)
O(n)
O(n)判断。
代码
#include<cstdio>#include<cstring>#include<algorithm>usingnamespace std;#define N 300010int a[N], f[N], s[2];intmain(){int n, i, sum =0, ans =0;scanf("%d",&n);for(i =1; i <= n; i++){scanf("%d",&a[i]);
sum += a[i];
s[i %2]+= a[i];}if(n %2==0){
s[0]> s[1]?printf("%d %d", s[0], sum - s[0]):printf("%d %d", s[1], sum - s[1]);}else{for(i =1; i <= n; i++){
i %2? f[i]= f[i -1]+ a[i]: f[i]= f[i -1]- a[i];}int l =0, r = sum, t =0;while(l <= r){int mid =(l + r)/2;int la =0;for(i =2; i <= n; i +=2){if(f[i -1]- la >= mid) la =min(la, f[i]);}if(f[n]- la >= mid) l = mid +1, t = mid;else r = mid -1;}printf("%d %d
", s[0]+ t, s[1]- t);}return0;}