打了一个飞舞随机化,在第107个点wa了,有没有dalao看看正确性
查看原帖
打了一个飞舞随机化,在第107个点wa了,有没有dalao看看正确性
744789
Big_Bishop楼主2023/10/27 19:16
#include<cstdio>
#include<algorithm>
#include<queue>
#include<random>
#include<ctime>
using namespace std;
typedef long long ll;
const int N=3e3+5;
int read(){
	int p=0;char ch=getchar();
	while(ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9') p=(p<<1)+(p<<3)+ch-'0',ch=getchar();
	return p;
}
struct node{
	int a,b;
}a[N];
int p,n,s;
int ans,an1[N],an2[N];
int now[N];
mt19937 myrand(123123);
int ra(int l,int r){
	return myrand()%(r-l+1)+l;
}
void pa(){
	shuffle(now+1,now+n,myrand);
	//for(int i=1;i<=n;i++) to[i]=now[i];
	int sum1=0,sum2=0;
	for(int i=1;i<=n;i++){
		if(i<=p){
			sum1+=a[now[i]].a;
		}
		else if(i<=p+s){
			sum2+=a[now[i]].b;
		}
	}
	int _=700000;
	while(_--){
		int o;
		if(p+s<n) o=_%3;
		else o=1;
		if(o==0) o=3;
		if(o==1){//交换p,s 
			int id1=ra(1,p),id2=ra(p+1,p+s);
			int s1=sum1,s2=sum2;
			s1=s1+a[now[id2]].a-a[now[id1]].a;
			s2=s2+a[now[id1]].b-a[now[id2]].b;
			if(s1+s2>sum1+sum2){
				swap(now[id1],now[id2]);
				sum1=s1,sum2=s2;
			}
		}
		else if(o==2){//交换p,没上的 
			int id1=ra(1,p),id2=ra(p+s+1,n);
			int s1=sum1;
			s1=s1+a[now[id2]].a-a[now[id1]].a;
			if(s1+sum2>sum1+sum2){
				sum1=s1;
				swap(now[id1],now[id2]);
			}
		}
		else if(o==3){//交换s,没上的 
			int id1=ra(p+1,p+s),id2=ra(p+s+1,n);
			int s2=sum2;
			s2=s2+a[now[id2]].b-a[now[id1]].b;
			if(s2+sum1>sum1+sum2){
				sum2=s2;
				swap(now[id1],now[id2]);
			}
		}
		if(sum1+sum2>ans){
			ans=sum1+sum2;
			for(int i=1;i<=p;i++) an1[i]=now[i];
			for(int i=p+1;i<=p+s;i++) an2[i-p]=now[i];
		}
	}
}
int main(){
	n=read(),p=read(),s=read();
	for(int i=1;i<=n;i++) a[i].a=read();
	for(int i=1;i<=n;i++) a[i].b=read();
	for(int i=1;i<=n;i++) now[i]=i;
	int _=222;
	while(_--) pa();
	printf("%d\n",ans);
	for(int i=1;i<=p;i++) printf("%d ",an1[i]);printf("\n");
	for(int i=1;i<=s;i++) printf("%d ",an2[i]);printf("\n");
	return 0;
}
2023/10/27 19:16
加载中...