D. Difference Array #808 div2

Array #808 div2"/>

D. Difference Array #808 div2

Problem - D - Codeforces

题意是给你一个序列a，让你每次做差分，然后排序，直到n等于1，输出这个值

QAQ 看了一位大佬的博客，清晰易懂（下面代码是学来的）

首先一眼题可以想到是差分+排序，每一次操作都排，但说实话不见得每次排序把所有元素全部排一遍，前面是0的可以忽略不计，因为不管怎么排，0始终在前面，所以只需要排后面的非零元素就好啦，然后上个代码，这个代码真的好看！！

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include<iostream>
#include<map>
#include<set>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
typedef pair<int,int> PAII;
typedef long long ll;
const int N=2e6+10,M=5050,mod=32767,INF=0x3f3f3f3f;
int a[N],b[N];
int n;
int main(){IOSint T;//T=1;cin>>T;while(T--){   int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];int pos=n;for(int i=1;i<=n;i++){if(a[i]){pos=i-1;break;}}while(n>1&&a[n-1])//如果倒数第二个数是0，也不用循环了，直接输出最后一个 {for(int i=max(1,pos);i<=n-1;i++) a[i]=a[i+1]-a[i];//pos可能是0，这个情况是没有0元素在的 n--;sort(a+pos,a+n+1);//这里的pos还没减1，就默认了从下标1开始了，已经默认+1if(pos>1) pos--;//如果前面有非零，就减少一位while(pos+1<=n&&a[pos+1]==0) pos++;//如果是0直接跳，一直到下一个数不是零为止，因为做差分是后一个数-前一个数 }cout<<a[n]<<"\n";}return 0;
}
/**/