首页 > 代码库 > bzoj 3043: IncDec Sequence 模拟

bzoj 3043: IncDec Sequence 模拟

2024-08-03 23:04:49   216人阅读

3043: IncDec Sequence

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 248  Solved: 139
[Submit][Status]

Description

给定一个长度为n的数列{a1,a2...an}，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。
问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。

Input

第一行一个正整数n 
接下来n行,每行一个整数,第i+1行的整数表示ai。
。

Output

第一行输出最少操作次数
第二行输出最终能得到多少种结果

Sample Input

4
1
1
2
2

Sample Output


1
2

HINT

 

对于100%的数据，n=100000，0<=ai<2147483648

 

　　正解传送门：http://blog.csdn.net/willinglive/article/details/38419573

　　我看到这道题时并没有想到正解，但是很容易yy出来修改策略，每次填满最低的那一段区间，像涨水一样一直涨到顶端，离散处理将低于x的所有值提升到x的增加次数，然后倒着在做一遍，如果暴力做的话肯定会TLE，我们观察每次增加的区间数量即为低于x的区间联通块数量，这不是涨水求联通数的裸题？。。。。

　　最后，因为我先离散化了所有点，所以如果我想回答询问2的话，需要回答离散之前的位置个数，这一点很容易wa。

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>using namespace std;#define MAXN 110000#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3fLLtypedef long long qword;int a[MAXN];pair<int,int> b[MAXN];int c[MAXN];int n,m;qword v1[MAXN],v2[MAXN];int uf[MAXN];int get_fa(int now){        return uf[now]==now ? now : uf[now]=get_fa(uf[now]);}int comb(int x,int y){        x=get_fa(x);        y=get_fa(y);        if (x==y)return false;        uf[x]=y;        return true;}int main(){        freopen("input.txt","r",stdin);        scanf("%d",&n);        int i,j,k;        for (i=0;i<n;i++)        {                scanf("%d",a+i);                b[i].first=a[i];                b[i].second=i;                c[i]=a[i];        }        sort(c,c+n);        m=unique(c,c+n)-c;        sort(b,&b[n]);        int nowc=0;        qword tot=0;        int x,y;        for (i=0;i<n;i++)uf[i]=i;        for (i=0;i<n;i++)        {                x=b[i].second;                tot++;                if (x && a[x-1]<=a[x])                        tot-=comb(x-1,x);                if (x<n-1 && a[x+1]<a[x])                        tot-=comb(x+1,x);                if (i!=n-1 && b[i+1].first!=b[i].first)                {                        v1[nowc+1]=v1[nowc]+tot*(c[nowc+1]-c[nowc]);                        nowc++;                }        }        nowc=m-1;        tot=0;        for (i=0;i<n;i++)uf[i]=i;        for (i=n-1;i>=0;i--)        {                x=b[i].second;                tot++;                if (x<n-1 && a[x+1]>=a[x])                        tot-=comb(x+1,x);                if (x && a[x-1]>a[x])                        tot-=comb(x-1,x);                if (i && b[i-1].first!=b[i].first)                {                        v2[nowc-1]=v2[nowc]+tot*(c[nowc]-c[nowc-1]);                        nowc--;                }        }        qword ans=INFL;        int mina=INF,maxa=-INF;        for (i=0;i<m;i++)        {                if (v1[i]+v2[i]<ans)                {                        ans=v1[i]+v2[i];                        mina=INF,maxa=-INF;                }                if (v1[i]+v2[i]==ans)                        mina=min(mina,c[i]),maxa=c[i];        }        printf("%lld\n%d\n",ans,maxa-mina+1);}

 

 

bzoj 3043: IncDec Sequence 模拟


联系
我们