2017 ACM/ICPC Asia Regional Shenyang Online 12 card card card

题目大意:

给出两个长度为n的序列A,B,从1开始依次加Ai,减Bi,分数为第一次为当前和为负数的位置以前的Ai之和(左闭右开区间)。同时有一种操作可以把当前的A1,B1移动到序列最后,注意序列A的各个元素之和等于B的各个元素之和。问取得最大分数时,至少应该操作多少次。如果分数相同,输出移动较少的次数;

基本思路:

出了以下前缀和,然后用一个sum(初始值为0)来当做判断条件,然后比这个小,就更新并记录一下下标,(每次更新说明和上一次更新这一段里的书是负数),然后最后输出下标,就是移动个数(前提是下标是从1开始的);

总结与反思:

有想过前缀和,但没想到这样怎么判断某一段是不是负数,好蠢啊,然后一定要掌握这种思路;

代码如下:

#include<cstdio>
#include<algorithm>
#include<iostream>

using namespace std;

const int maxn = 2000000+10;

ll ans[maxn];

int main()
{
    while(scanf("%d",&n)==1)
    {
        for(int i=1;i<=n;i++) scanf("%lld",&ans[i]);
        ll x;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&x);
            ans[i]-=x;
        }
        for(int i=2;i<=n;i++) ans[i]+=ans[i-1];
        ll sum=0;
        int res=0;
        for(int i=1;i<=n;i++)
        {
            if(ans[i]<sum)
            {
                sum=ans[i];
                res=i;
            }
        }
        printf("%d
",res%n);
    }
    return 0;
}

  

原文地址:https://www.cnblogs.com/imzscilovecode/p/7505063.html