P76030 两端取牌 — 题解

专题： 双指针
适用题目： 新生 OJ 本地题包中的 P76030，不要直接用于外站同名题。

解题思路

双指针分别指向两端，每回合把较大端拿走并移动该端指针，两个玩家轮流累加。

复杂度

时间 $O(n)$，额外空间 $O(n)$。

易错点

两端相等时必须选择左端，且先手后手分别计分。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int main(void) {
    int n;scanf("%d",&n);long long *a=malloc(n*sizeof(long long));
    for(int i=0;i<n;i++)scanf("%lld",&a[i]);
    int l=0,r=n-1,turn=0;long long score[2]={0,0};
    while(l<=r){
        if(a[l]>=a[r])score[turn]+=a[l++];
        else score[turn]+=a[r--];
        turn^=1;
    }
    printf("%lld %lld\n",score[0],score[1]);free(a);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<ll>a(n);
    for(auto &x:a)cin>>x;
    int l=0,r=n-1;
    ll scores[2]={
    }
    ;
    for(int t=0;l<=r;t^=1){
        if(a[l]>=a[r])scores[t]+=a[l++];
        else scores[t]+=a[r--];
    }
    cout<<scores[0]<<' '<<scores[1]<<nl;
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。