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\n",res%n);

    }

    return 0;

}

巴特西

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

最新文章

热门文章