BZOJ3043: IncDec Sequence 贪心+差分
题解：
懒得写题解了，安利一下大爷题解吧。
http://blog.csdn.net/popoqqq/article/details/43926515
代码：
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100010
long long a[N];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=n;i>=1;--i)
a[i]-=a[i-1];
long long up=0,down=0;
for(int i=2;i<=n;++i)
if(a[i]>0)
up+=a[i];
else
down-=a[i];
cout<<max(up,down)<<endl<<((up>down?up-down:down-up)+1)<<endl;
return 0;
}
评论 (0)