首页 > 代码库 > Codeforces Round #424 (Div. 2） D 思维 E set应用,树状数组
Codeforces Round #424 (Div. 2） D 思维 E set应用,树状数组
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把钥匙应该是连续的。
然后，就是瞎暴力。。
#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 secondtypedef 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\n", 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 secondtypedef 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\n", ans); return 0;}
Codeforces Round #424 (Div. 2） D 思维 E set应用,树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。