bzoj3043IncDec Sequence*

bzoj3043IncDec Sequence

题意：

n个数，每次可以将区间l到r里的数+1或-1，问将它们变成同个数的最小操作次数和保证最小操作次数前提下有多少中可能。n≤100000。

题解：

先对原数组差分（得到的数组第一个为原数组第一个元素，之后的元素为原数组相邻元素之差），则原操作变为左右端点对应元素加1减1或减1加1，求最小操作次数使得除第一个元素之外剩下元素均为0。则先将正负数对消，剩下的数可以自己消掉或与第一个数对消，故第一问答案为max(正数之和,负数绝对值之和) 第二问答案为abs(正数之和-负数绝对值之和)+1。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100010
#define ll long long
using namespace std;

inline ll read(){
    char ch=getchar(); ll f=1,x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f*x;
}
int n; ll day,xiy,a,b;
int main(){
    n=read(); a=read(); inc(i,2,n){b=read(); if(b-a>0)day+=(b-a);else xiy+=(a-b); a=b;}
    printf("%lld\n%lld",max(day,xiy),abs(day-xiy)+1); return 0;
}

 

20160929