time
题解
贪心考虑,考试时想错了,我想的是移动最大值,枚举最大值位置,然后把左面和右面逆序对拼起来,
当然,处理不了有多个最大值情况,于是我就想着打个部分分吧
然而对拍还是挂,
枚举最大值位置是不对的
考虑一种情况a,b,c,d,e,f,g
其中d最大可能出现a移动到d右面更优,b,c留在左面,我只移动最大值的话默认a,b,c都在左面
附赠一组点4 5 2 3 1 6 7 最优决策是6步,方案是2 4 5 6 7 3 1 .
出现了我说的这种情况
考试时打这个题花费时间还是过于多了
正解是贪心移动最小值,这样是保证正确的,只移动最大值相当与限制了一些情况出现
然后最小值考虑了所有情况且一定正确
正难则反__by yangguangjie
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 111111 ll p[A],a[A],b[A],c1[A],c2[A]; ll n,ans=0; vector <ll> v[A]; //正 void add1(ll x,ll d){for(ll i=x;i!=0&&i<=100000;i+=i&-i) c1[i]+=d;} ll ask1(ll x,ll ans=0){for(ll i=x;i>=1;i-=i&-i) ans+=c1[i];return ans;} //逆 void add2(ll x,ll d){for(ll i=x;i>=1;i-=i&-i) c2[i]+=d;} ll ask2(ll x,ll ans=0){for(ll i=x;i!=0&&i<=100000;i+=i&-i) ans+=c2[i];return ans;} void sol(){ for(ll i=1;i<=n;i++){ add1(i,1);add2(i,1); v[a[i]].push_back(i); } for(ll i=1;i<=100000;i++){ if(v[i].size()){ for(ll fr=0,ba=v[i].size()-1;fr<=ba;){ ll x=v[i][fr],y=v[i][ba]; ll l=ask1(x-1),r=ask2(y+1); // printf("l=%lld r=%lld ",l,r); if(l<r){ ans+=l; add1(x,-1); add2(x,-1); fr++; } else { ans+=r; add1(y,-1); add2(y,-1); ba--; } } } } } int main(){ freopen("time.in","r",stdin); freopen("time.out","w",stdout); scanf("%lld",&n); for(ll i=1;i<=n;i++) scanf("%lld",&a[i]),p[i]=i; sol(); printf("%lld ",ans); }
game
题解
做过一个类似的题(老司机的狂欢),也是求字典序最小,也是第一问特别简单,然后根据第一问推第二问
但实在没想到可以每一位上二分求字典序最小
推单调性
如果upper_bound有值具有单调性,当前选的值越大,以后高的可能性就越小
如果upper_bound没值具有单调性,当前选的值越大,以后得分高的可能越小
但是函数是分段的
可以分两次二分
这样每次set暴力check复杂度$n^2*{log}^2$
现在思考如何check
可以用权值线段树维护
维护A的没用上的牌
维护B的没用上的牌
向上合并时右子树每一张A都可以于左子树中B匹配
代码大致是这样
void up(ll x){ ll de=min(tr[x<<1|1].L,tr[x<<1].R); tr[x].s=tr[x<<1].s+tr[x<<1|1].s+de; tr[x].L=tr[x<<1].L+tr[x<<1|1].L-de; tr[x].R=tr[x<<1].R+tr[x<<1|1].R-de; }
代码
#include<bits/stdc++.h> using namespace std; #define ll int #define A 1010100 #define maxx 100000 ll read(){ll x;scanf("%d",&x);return x;} ll tot,n; ll b[A],a[A]; multiset<ll> st; multiset<ll> ::iterator it; struct node{ ll l,r,L,R,s; //L:A的牌 //R:B的牌 //s得分 }tr[A]; void built(ll x,ll l,ll r){ tr[x].l=l,tr[x].r=r; if(l==r){ return ; } ll mid=(l+r)>>1; built(x<<1,l,mid); built(x<<1|1,mid+1,r); } void up(ll x){ ll de=min(tr[x<<1|1].L,tr[x<<1].R); tr[x].s=tr[x<<1].s+tr[x<<1|1].s+de; tr[x].L=tr[x<<1].L+tr[x<<1|1].L-de; tr[x].R=tr[x<<1].R+tr[x<<1|1].R-de; } void insert(ll x,ll pla,ll vala,ll valb){ if(tr[x].l==tr[x].r){ tr[x].L+=vala; tr[x].R+=valb; return ; } ll mid=(tr[x].l+tr[x].r)>>1; if(mid>=pla) insert(x<<1,pla,vala,valb); else insert(x<<1|1,pla,vala,valb); up(x); } void getans(ll now){ insert(1,b[now],0,-1); ll l=b[now]+1,r=*st.rbegin(),ans=0; while(l<=r){ ll mid=(l+r)>>1; insert(1,mid,-1,0); if(tr[1].s+1==tot){ l=mid+1; ans=mid; } else r=mid-1; insert(1,mid,1,0); } insert(1,ans,-1,0); if(tr[1].s+1==tot){ tot--; printf("%d ",ans); it=st.find(ans); st.erase(it); return ; } insert(1,ans,1,0); l=1,r=b[now],ans=0; while(l<=r){ ll mid=(l+r)>>1; insert(1,mid,-1,0); if(tr[1].s==tot){ l=mid+1; ans=mid; } else r=mid-1; insert(1,mid,1,0); } insert(1,ans,-1,0); printf("%d ",ans); it=st.find(ans); st.erase(it); } int main(){ freopen("game.in","r",stdin); freopen("game.out","w",stdout); n=read(); built(1,1,maxx); for(ll i=1;i<=n;i++){ b[i]=read(); insert(1,b[i],0,1); } for(ll i=1;i<=n;i++){ a[i]=read(); insert(1,a[i],1,0); st.insert(a[i]); } tot=tr[1].s; for(ll i=1;i<=n;i++){ getans(i); } }