526互联

Codeforces Global Round 3

发布时间 2023-10-07 09:23:29作者: gan_coder

C题就是考虑利用1，n两个端点就好，有些细节要特判。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define A puts("Yes")
#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N=3e5+5;
struct node{
	int l,r;
};
node b[N*5];
int a[N],n,tot,p[N],x;
void S(int l,int r){
	b[++tot]=(node){l,r};

	p[a[l]]=r;
	p[a[r]]=l;
	swap(a[l],a[r]);
}
int main()
{
//	freopen("data.in","r",stdin);
	scanf("%d",&n);
	fo(i,1,n) scanf("%d",&a[i]),p[a[i]]=i;
	
	fo(i,1,n) {
		if (a[i]==i) continue;
		
		x=p[i];
		if (x-1>=n/2) {
			S(1,x);
			if (i-1>=n/2) S(1,i),S(x,1);
			else{
				S(1,n); S(n,i);
				if (a[1]!=1) S(x,1);
			}
		}
		else{
			S(x,n);
			if (n-i>=n/2) S(n,i),S(n,x);
			else{
				S(1,n); S(1,i);
				if (a[n]!=n) S(x,n);
			}
		}
	}
	
	printf("%d\n",tot);
	fo(i,1,tot) printf("%d %d\n",b[i].l, b[i].r);
	
	return 0;
}

D题首先想到根据a<b和a>b分成两种类型
不妨考虑a<b
a1< b1 >a2< b2 >b3>a4
如果能够限制b1>b2>b3那么这个限制就一定能够满足，又因为这些数都是两两不同，所以一定可以通过排序满足，并且就是能得到的最大值。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define A puts("Yes")
#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N=3e5+5;
struct node{
	int b,id;
};
node a[N],b[N];
int n,x,y,tot2,tot1;
bool cmp1(node a,node b){
	return a.b>b.b;
}
bool cmp2(node a,node b){
	return a.b<b.b;
}
int main()
{ 
//	freopen("data.in","r",stdin);
	scanf("%d",&n);
	fo(i,1,n){
		scanf("%d %d",&x,&y);
		if (x<y) a[++tot1]=(node){y,i};
		else b[++tot2]=(node){y,i};
	}
	sort(a+1,a+tot1+1,cmp1);
	sort(b+1,b+tot2+1,cmp2);
	if (tot1>=tot2) {
		printf("%d\n",tot1);
		fo(i,1,tot1) printf("%d ",a[i].id);
	}
	else{
		printf("%d\n",tot2);
		fo(i,1,tot2) printf("%d ",b[i].id);
	}
	
	return 0;
}