1367: [Baltic2004]sequence
Time Limit: 20 Sec Memory Limit: 64 MB
Submit: 521 Solved: 159
[Submit][Status]
Description
Input
Output
一個整數R
Sample Input
7
9
4
8
20
14
15
18
Sample Output
13
HINT
所求的Z序列為6,7,8,13,14,15,18.
R=13
左偏樹+1
這題裸裸的左偏樹,我卻各種WA。。。。
結果發現 左偏樹合並 a*b==0 會乘爆掉。。。掉節操。。。。。
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (1300000+10) long long mul(long long a,long long b){return (a*b)%F;} long long add(long long a,long long b){return (a+b)%F;} long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} typedef long long ll; int father[MAXN]; int getfather(int x) { if (father[x]==x) return x; father[x]=getfather(father[x]); return father[x]; } struct node { ll v; int dis,ch[2]; node():v(0),dis(0){ch[0]=ch[1]=0;} node(ll _v):v(_v),dis(0){ch[0]=ch[1]=0;} }q[MAXN]; int merge(int a,int b) { if (a==0||b==0) return a+b; if (q[a].v<q[b].v) swap(a,b); q[a].ch[1]=merge(q[a].ch[1],b); if (q[q[a].ch[0]].dis<q[q[a].ch[1]].dis) swap(q[a].ch[0],q[a].ch[1]); if (q[a].ch[1]) q[a].dis=q[q[a].ch[1]].dis+1;else q[a].dis=0; return a; } int root[MAXN],tot=0; int pop(int a) { int p=merge(q[a].ch[0],q[a].ch[1]); return p; } int n,siz[MAXN],l[MAXN],r[MAXN]; ll a[MAXN]; ll abs2(ll a,ll b){return a-b>0?a-b:b-a;} int main() { // freopen("bzoj1367.in","r",stdin); scanf("%d",&n); For(i,n) scanf("%lld",&a[i]),a[i]-=(long long)i,father[i]=i,q[i].v=a[i]; For(i,n) { siz[++tot]=1;root[tot]=i;l[tot]=r[tot]=i; while (tot>1&&q[root[tot]].v<=q[root[tot-1]].v) { int ru=root[tot-1],rv=root[tot]; Fork(j,l[tot],r[tot]) { q[j]=node(a[j]); ru=merge(ru,j); } siz[tot-1]+=r[tot]-l[tot]+1;r[tot-1]=r[tot];tot--; while (siz[tot]>(r[tot]-l[tot]+2)/2) ru=pop(ru),siz[tot]--; root[tot]=ru; } // For(i,tot) cout<<l[i]<<' '<<r[i]<<' '<<q[root[i]].v<<endl; cout<<endl; } //For(i,n) cout<<a[i]<<' ';cout<<endl; //For(i,tot) cout<<siz[i]<<' ';cout<<endl; //For(i,tot) cout<<l[i]<<' '<<r[i]<<' '<<q[root[i]].v<<endl; ll ans=0; For(i,tot) { Fork(j,l[i],r[i]) ans+=abs2(q[root[i]].v,a[j]); } printf("%lld\n",ans); return 0; }
第二Sol-貪心:
假想有2數列A,B
A的中位數<B的中位數
A的中位數>(B+C)的中位數
則(A+B+C)的中位數≤A的中位數<B的中位數
所以A中位數,B中位數往上的部分去掉,不影響結果
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define MAXN (1000000+10) typedef long long ll; struct node { int v,dis,ch[2]; node():v(0),dis(0){ch[0]=ch[1]=0;} node(int _v):v(_v),dis(0){ch[0]=ch[1]=0;} }q[MAXN]; int merge(int a,int b) { if (a==0||b==0) return a+b; if (q[a].v<q[b].v) swap(a,b); q[a].ch[1]=merge(q[a].ch[1],b); if (q[q[a].ch[0]].dis<q[q[a].ch[1]].dis) swap(q[a].ch[0],q[a].ch[1]); q[a].dis=q[q[a].ch[1]].dis+1; return a; } int root[MAXN],tot=0; int pop(int a) { int p=merge(q[a].ch[0],q[a].ch[1]); return p; } int n,siz[MAXN]={0},l[MAXN]={0},r[MAXN]={0}; int a[MAXN]={0}; ll abs2(ll a,ll b){return a-b>0?a-b:b-a;} int main() { freopen("bzoj1367.in","r",stdin); scanf("%d",&n); For(i,n) { scanf("%d",&a[i]),a[i]-=i;q[i].v=a[i]; } For(i,n) { siz[++tot]=1;root[tot]=i;l[tot]=r[tot]=i; while (tot>1&&q[root[tot-1]].v>q[root[tot]].v) { int ru=root[tot-1],rv=root[tot]; /* Fork(j,l[tot],r[tot]) { q[j]=node(a[j]); ru=merge(ru,j); }*/ ru=merge(ru,rv);int b=((r[tot-1]-l[tot-1]+1)%2)+((r[tot]-l[tot]+1)%2); siz[tot-1]+=siz[tot];r[tot-1]=r[tot];tot--; if (b==2) ru=pop(ru),siz[tot]--; root[tot]=ru; // For(i,tot) cout<<l[i]<<' '<<r[i]<<' '<<q[root[i]].v<<endl; cout<<endl; } } // For(i,n) cout<<a[i]<<' ';cout<<endl; // For(i,tot) cout<<siz[i]<<' ';cout<<endl; // For(i,tot) cout<<l[i]<<' '<<r[i]<<' '<<q[root[i]].v<<endl; ll ans=0; For(i,tot) { Fork(j,l[i],r[i]) ans+=abs2(q[root[i]].v,a[j]); } cout<<ans<<endl; return 0; }