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;
}

View Code

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;
}

View Code

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;
}

View Code