CodeForces - 820D 思维好题

59 阅读 0 评论 39 点赞

我是靠谱客的博主神勇大米，最近开发中收集的这篇文章主要介绍CodeForces - 820D 思维好题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

感谢Joovodalao的解释，让我理解了一下这道题的p数组更新。
题意：
给你n个数，每次可以向前移动一次数组，就相当于1，2，3，4，5 移动一次变成5，1，2，3，4一样，现在要你算出1到n的a[i]-i的最小和。
题解：
我要说的基本在我的代码里了，详细的请边看代码边看注释，这是一道非常不错的题目，这道题的关键是数组p[i]表示的是有多少个数需要向右边移动i步到达目标位置(也可以理解成多少个数在目标位置的左边)，这里解释一下什么是目标位置，就是说假如一个数组：5，2，4，1，3，那么5的目标位置就是在5，它距离目标位置5-1步。还有一点需要注意的就是，不管移动多少次都是以原始数组为前提的，而非移动之后的状态，想这道题的时候一定要记得这点，我就是老是以移动之后的状态去想下一步，发现很难理解。
题外话：
网上看了挺多的，奈何都没有我想要的那种比较容易理解的答案，所以只能硬啃着思考，然后把自己思考所得的东西分享出来，期间让我感到意外的是，我的朋友居然关注着我的破博客，然后果然狠狠的吐槽了一番，说什么跟网上其他的差不多，
废话。。。。。我不会啊，只能参考dalao的博客了。。事实证明说这话死的更严重，也挺对的，最近已经开始反思了，为什么我死学了一个月还是没长进甚至退步了呢？这可能跟我不愿意花多点时间停留在一道题上的原因有关，
一旦超过半小时就百度，而且还是直接看代码的那种，导致了我实际上并没有做这道题，使我的实力没有出现进步反而退步了，有一些经典的题是真的做一点少一点，而我却不知道珍惜，乱百度，浪费了进步的空间，现在我的会
重新认真起来，不为别的就为那位关注着我的朋友的吐槽而行动。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define LL long long int 
const int MAXN=1e6+7;
int a[MAXN],p[MAXN];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(a,0,sizeof(a));
        memset(p,0,sizeof(p));
        int l=0,r=0;
        LL sum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]>=i)
            p[a[i]-i]++,l++;//l记录的是a[i]>=i的个数，深层的含义就是a[i]在目标位置的左边，而p[i]表示的是有多少个数需要移动i步到达目标位置。 
            else
            r++;//同理可得到r表示的是a[i]在目标位置的右边。 
            sum=sum+abs(a[i]-i);
        }
        LL ans=sum;
        int d=0;
        for(int i=1;i<n;i++)
        {
            l=l-p[i-1];//表示的是数组向前移动一步，那么l就要减去之前距离目标位置i-1步的数的个数。 
            r=r+p[i-1];//那么r就相当于增加了之前距离目标位置i-1步的数的个数了。 
            sum=sum-l+r-abs(a[n-(i-1)]-(n+1))+abs(a[n-(i-1)]-1);//这里解释一下sum-l+r，l就相当于a[i]>=i的数量，那么向前移动的话L必然减少，
                                                                //那么同理可得向前移动的话r必然会增加。为什么会增加？因为负数减去更大的数得到的绝对值肯定更大啊。               
                                                                //然后就是sum-abs(a[n-(i-1)]-(n+1))+abs(a[n-(i-1)]-1);为什么是a[n-(i-1)]-(n+1))呢？这是因为前面已经减去了l，这就相当于整个数组向前挪动了一位，那么最后一位就相当于去到了n+1位哪里，
                                                                //那么我们就要减去最后一位与n+1位置的贡献，加上最后一位与1的贡献。 
            p[(a[n-(i-1)]+(i-1))%n]++;//至于这一步我目前还没清楚，等我去问问一下，别人的博客上说的是p[i]表示初始数组中有多少个数在它目标左边第i个位置上，那么我的理解就是a[n-(i-1)]这个数从原本数列中的位置向右边移动，需要移动多少位到达目标位置，
                                      //那么就能解释为什么是+(i-1)了，比如你42135，最后一位5从原始位置需要想右边移动5次（超过n会%n的）才能达到目标位置，所以p[5]++. 
                                      //听dalao说这行的p[(a[n-(i-1)]+(i-1))%n]中的+(i-1)中的i-1是因为有可能原数组最小和是不用移动所以才是i-1的（因为是i是从1开始跑的）。。。。。
            l++;//l++,r--是因为最后一个数从最后一个位置去到了第一个位置，那么相应的l++，r--. 
            r--;
            if(ans>sum)
            {
                ans=sum;
                d=i;
            }
        }
        printf("%lld %dn",ans,d);
    }
}