首页 > 代码库 > bzoj 3043: IncDec Sequence 模拟
bzoj 3043: IncDec Sequence 模拟
3043: IncDec Sequence
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 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
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 模拟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。