Codeforces Global Round 3
A-水题，a+b组合+ab+剩余的放头或者尾...注意long long
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int main(){ long long a,b,c; while(~scanf("%lld%lld%lld",&a,&b,&c)){ if (a==b){ printf("%lld\n",2*c+2*b); }else { printf("%lld\n",2*c+2*min(a,b)+1); } } return 0; }
B. Born This Way*
当时怎么也没想出来。。。
因为题目是按顺序给的，多半是二分。
当时的确想到二分，但是没有想好改如何二分
正确做法应该是枚举A->B航班的取消个数
要取消A->B航班的最好效果是把前i(枚举个数)个删除，
那么二分的去找第一个大于等于A->B航班的第i+1次航班的到达时间
如果还可以删除k-i个航班的话，从这个位置往后删除是最优的。
最后二分答案即可
#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; const int maxx = 2e5+7; int a[maxx]; int b[maxx]; int main(){ int n,m; int ta,tb,k; while(~scanf("%d%d%d%d%d",&n,&m,&ta,&tb,&k)){ for (int i=1;i<=n;i++){ scanf("%d",&a[i]); } for (int i=1;i<=m;i++){ scanf("%d",&b[i]); } int ans=0; if (k>=n || k>=m){ printf("-1\n"); continue; } for (int i=0;i<=k;i++){ int pos=lower_bound(b+1,b+1+m,a[i+1]+ta)-b; pos+=(k-i); if (pos>m){ printf("-1\n"); return 0; } else { ans=max(ans,b[pos]+tb); } } printf("%d\n",ans); } return 0; }
C. Crazy Diamond*
好题！！！可能是我太菜了。。。
给出乱序的1-N的数字
题目要求把现在位置进行排序，每次可以交换两个位置，这个两个位置差必须大于n/2
当时没有想到考虑|i-j|>=n/2
如果这个i是n/2的话，j只能是n
如果这个位置是n/2+1的话，j只能是1
那么就非常容易看出来了，我们应该从中间往两边的走，因为越靠近中间的位置，要求越高
记录每个数值i对应的位置pos[i]
给一个左指针L，右指针R，往两边扩展，1和n一定是最后进来的
那么对于左位置L来说，如果a[L]!=L那么pos[L]有三种位置
pos[L]在L的右边并且位置查大于n/2，pos[L]->L
pos[L]<L，代表要的位置在L的左边,pos[L]->n->L
pos[L]>L,并且位置差小于L/2,pos[L]->1->N->L
右边同理,vector+pair保存答案即可
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<map> #include<vector> #define mp make_pair #define pii pair<int,int> using namespace std; const int maxx = 3e5+7; int a[maxx]; int pos[maxx]; vector<pii>ans; void change(int x,int y){ ans.push_back(mp(x,y)); swap(pos[a[x]],pos[a[y]]); swap(a[x],a[y]); } int main(){ int n; while(~scanf("%d",&n)){ for (int i=1;i<=n;i++){ scanf("%d",&a[i]); pos[a[i]]=i; } for (int i=n/2;i>=1;i--){ int l=i,tmp; int r=n-i+1; if (a[l]!=l){ if (pos[l]-l>=n/2){ change(l,pos[l]); }else { if (pos[l]<l){ change(pos[l],n); change(n,l); }else { change(pos[l],1); change(1,n); change(n,l); } } } if (a[r]!=r){ if (r-pos[r]>=n/2){ change(r,pos[r]); }else { if (pos[r]>r){ change(pos[r],1); change(1,r); }else { change(pos[r],n); change(n,1); change(1,r); } } } } printf("%d\n",ans.size()); for (int i=0;i<ans.size();i++){ printf("%d %d\n",ans[i].first,ans[i].second); } } return 0; }
