100分求助
查看原帖
100分求助
515833
tang_mx楼主2023/10/11 13:00

第一二个hack数据 T 了,求帮看看怎么改qwq

https://www.luogu.com.cn/paste/bgtb7zq6

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#define p1 p<<1
#define p2 p<<1|1

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;

const int N=1e5+10;
const int inf=2147483647;
const int mod=998244353;

inline int read(){
	int x=0,y=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')y=-y;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+(c^'0');c=getchar();}
	return x*y;
}

PII q[N];   //廊桥 
PII q1[N];

int siz[N],siz1[N];

int s1[N],s[N],ans[N],ans1[N]; 

bool cmp(PII a,PII b){return a.first<b.first;}

bool cmp1(int a,int b){return a>b;}

int main(){
//	freopen("airport.in","r",stdin);
//	freopen("airport.out","w",stdout);
	int n,m1,m2;
	n=read(),m1=read(),m2=read();
	PII ap1[N],ap2[N];   //飞机
	for(int i=1;i<=m1;i++)ap1[i].first=read(),ap1[i].second=read();
	for(int i=1;i<=m2;i++)ap2[i].first=read(),ap2[i].second=read();
	
	// 思路是按照 先到先得 分配廊桥,为使得每个廊桥能停的飞机最多,进行贪心 
	
	sort(ap1+1,ap1+m1+1,cmp);sort(ap2+1,ap2+m2+1,cmp); //按照 先到先入 排序
	
	int cnt=0;
	for(int i=1;i<=m1;i++){
		bool flag=0;
		for(int j=1;j<=cnt;j++){
			if(ap1[i].first>q[j].second){// 贪心选 最优廊桥 
				q[j]=ap1[i];siz[j]++;flag=1;break;
			}
		}
		
		if(flag)continue;
		q[++cnt]=ap1[i];  // 无法分入现有廊桥,开新廊桥 
		siz[cnt]++;
	}
	//依次将 飞机 放到每个最优廊桥 
	
//	for(int i=1;i<=cnt;i++)ans[i]=q[i].size();
	// 记录每个廊桥能停多少飞机 
	
	//对国际机场操作同上 
	cnt=0;
	for(int i=1;i<=m2;i++){
		bool flag=0;
		for(int j=1;j<=cnt;j++){
			if(ap2[i].first>q1[j].second){
				q1[j]=ap2[i];siz1[j]++;flag=1;break;
			}
		}
		if(flag)continue;
		q1[++cnt]=ap2[i];
		siz1[cnt]++;
	}
//	for(int i=1;i<=cnt;i++)ans1[i]=q1[i].size();
	
	for(int i=1;i<=m1;i++)s[i]=s[i-1]+siz[i];   // 前缀和 
	for(int i=1;i<=m2;i++)s1[i]=s1[i-1]+siz1[i];
	
	
	int sum=0;
	for(int i=0;i<=n;i++)sum=max(sum,s[min(i,m1)]+s1[min(n-i,m2)]);
	printf("%d",sum);
	return 0;
}
2023/10/11 13:00
加载中...