Codeforces Round #424 (Div. 2, rated, based on VK Cup Finals)
D. Office Keys
题意：一条直线上，有个办公室坐标 p，有 n个人在a[i]，有 k把钥匙在b[i]，每个人必须拿到一把钥匙，然后到办公室。问怎么安排花的时间最短。
tags：还是不懂套路啊。。其实多画两下图就能够感觉出来，2333
关键是要看出来，n个人拿的 n把钥匙应该是连续的。
然后，就是瞎暴力。。
还可以直接二分时间，对于每个时间，所有人从左往右顺序，让一个人 xi 尽量往左边取，这样才不会影响影响他右边的人。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 2005; int n, k; ll p, a[N], b[N]; int main() { scanf("%d %d %lld", &n, &k, &p); rep(i,1,n) scanf("%lld", &a[i]); rep(i,1,k) scanf("%lld", &b[i]); sort(a+1, a+1+n); sort(b+1, b+1+k); ll ans=1e18; for(int cb=1; cb+n-1<=k; ++cb) { ll ans1=0; rep(i,1,n) { ans1 = max(ans1, abs(a[i]-b[cb+i-1])+abs(b[cb+i-1]-p)); } ans=min(ans, ans1); } printf("%lld ", ans); return 0; }
E. Cards Sorting
题意：n 个数，操作：每次取出头一个数，如果是这些数中最小的就删除，如果不是就放到底部。 问要多少次操作才能全部删除这 n个数。
tags：利用set和树状数组，快速模拟操作。一开始思路错了，想的是for一遍，每个数的会对前面比它大的数产生贡献，最后发现不行，白折腾半小时，心累
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 100005; struct Bit { int bi[N]; void add(int x, int y) { for(; x<N; x+=x&-x) bi[x]+=y; } ll sum(int x) { ll ans=0; for(; x>0; x-=x&-x) ans+=bi[x]; return ans; } }bit; int n, a[N]; set<int > se[N]; int main() { scanf("%d", &n); rep(i,1,n) { scanf("%d", &a[i]); se[a[i]].insert(i); bit.add(i, 1); } ll ans=0; int now=1, mi=1; rep(ci,1,n) { while(se[mi].empty()) ++mi; if(se[mi].lower_bound(now)!=se[mi].end()) { int pos=now; now = *se[mi].lower_bound(now); ans += bit.sum(now)-bit.sum(pos-1); } else { int pos=now; now = *se[mi].lower_bound(1); ans += bit.sum(n)-bit.sum(pos-1)+bit.sum(now); } se[mi].erase(now); bit.add(now, -1); } printf("%lld ", ans); return 0; }