写了个假算法
查看原帖
写了个假算法
344723
Ssyy楼主2021/5/19 13:24

我大概写了个假算法? 快读+吸氧才从60分涨到90分。 T一个560ms/500ms 一直想在递归里把输赢结果赋上,但没成功。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#define INF 0x3f3f3f3f 

typedef long long ll;
using namespace std;


int N,R,Q;
int a,b;



typedef struct {
	int a,b,id;
	//number,score,strength;
}Node;

Node p[400010]={{0,0}};
Node temp[400010]={{0,0}};


bool cmp(Node a,Node b){
//	return a.a>b.a || (a.a==b.a && a.id < b.id);
	if(a.a==b.a)
		return a.id < b.id;
	return a.a>b.a;
}
inline int read(){//快读
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
		while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
		return s*w;
	}
	

void mergesort(int l,int r){
	
	if(l==r)	return;
	
	
	int mid=(l+r)/2;
	int i=l;
	int k=l;
	int j=mid+1;
	mergesort(l    ,mid);
	mergesort(mid+1,r  );
	
	while(i<=mid && j<=r){
		if(cmp(p[i],p[j]))	temp[k++]=p[i++];
		else 				temp[k++]=p[j++];
	}
	while(i<=mid)			temp[k++]=p[i++];
	while(j<=r)				temp[k++]=p[j++];
	
	for(i=l;i<=r;i++)	p[i]=temp[i];
	
	
}

void print(){
	cout << R << ":";
	for(int i=1;i<=N;i++){
		printf("%d ",p[i].id);
	}
	cout << "\n";
}
int main() {
	
	cin >> N >> R >> Q;
	N*=2;
	for(int i=1;i<=N;i++){
		p[i].a=read();
		p[i].id=i;
	}
	for(int i=1;i<=N;i++){
		p[i].b=read();
	}
	stable_sort(p+1,p+N+1,cmp);
	while(R--)	{
		for(int i=1;i<N;i+=2){
			if(p[i].b > p[i+1].b)	p[i].a++;
			if(p[i].b < p[i+1].b)	p[i+1].a++;
			
			if(cmp(p[i+1],p[i])){
				swap(p[i],p[i+1]);
			}
		}
		mergesort(1,N);
	}
	stable_sort(p+1,p+N+1,cmp);
	cout << p[Q].id;
}
2021/5/19 13:24
加载中...