CodeForces 1669 F.Eating Candies"/>
CodeForces 1669 F.Eating Candies
原题链接:
Problem - 1669F - Codeforces
洛谷上有题干翻译~
链接:Eating Candies - 洛谷 | 计算机科学教育新生态 (luogu)
题意
有 n 个糖果从左往右放在桌子上, Alice 和 Bob 吃糖果, Alice可以从左边开始吃, Bob可以从右边开始吃,他们需要连续吃,不能跳过任何一颗糖果,如果 Alice 吃掉了糖果, Bob 就不能吃,反之亦然,他们的目标是吃到等重的糖果。
输入
第一行是一个整数 t 表示测试样例的数量,接下来的每一组样例的第一行是一个整数n 表示糖果数量,第二行是 n 个整数w1,w2.,..,wn ,表示从左往右的糖果重量。
输出
对于每组测试样例,输出一个整数,表示他们同时能吃到的最多糖果数
输入输出样例
输入:
4
3
10 20 10
6
2 1 4 2 4 1
5
1 2 4 8 16
9
7 3 20 5 15 1 11 8 10
输出:
2
6
0
7
ac代码
#include<bits/stdc++.h>
using namespace std;
int t,n;
int w[200005];
int main()
{cin >> t;while(t--){
// int num=0;int sum=0,ans=0,i=0,j=0;cin>>n;for(i=0;i<n;i++) cin>>w[i]; for(i=0,j=n-1; i<=j;){if(sum>0) sum-=w[j--];else sum+=w[i++];if(sum==0) ans=i+n-j-1;
// sum+=w[j--]; 这样算是对称的 但是按理来说不是对称的
// num+=w[i++];
// if(sum==num)
// ans=i+n-j-1;}cout<<ans<<endl;}return 0;
}
反思:
注释掉的部分是我第一个wa的代码,我开始的思路是这样的,但这个思路不正确,这么算的话是按照alice一个bod一个糖果算的,但样例中就可以看出bob和alice吃的数量可以不一样,我们只需要找的是最大摄入糖果量。所以我们只需要设置一个变量,双指针;待变量为0的时候计算i和j走了多少即为答案。
更多推荐
CodeForces 1669 F.Eating Candies
发布评论