社区讨论

数据需要加强。

P7913[CSP-S 2021] 廊桥分配参与者 5已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lobi42jn
此快照首次捕获于
2023/10/29 21:22
2 年前
此快照最后确认于
2023/11/04 02:35
2 年前
查看原帖
rt n2n^2 算法实测可过。
Code :
CPP
//champion zzl will not run!!1
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <vector>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define ll long long

inline int read() {
	int x = 0,f = 1;char c = getchar();
	while (!isdigit(c)) {if (c == '-') {f = -1;}c = getchar();}
	while (isdigit(c)) {x = x * 10 + c - 48;c = getchar();} 
	return x * f;
}

const int N = 1e5 + 10;

int n,m1,m2,t[N],buc1[N],buc2[N];
pii q1[N],q2[N];


signed main() {
	//freopen("airport.in","r",stdin);
	//freopen("airport.out","w",stdout);
	
	n = read();m1 = read();m2 = read();
	for (int i = 1;i <= m1;++i) {
		q1[i].first = read();q1[i].second = read();
	}
	for (int i = 1;i <= m2;++i) {
		q2[i].first = read();q2[i].second = read();
	}	
	sort(q1+1,q1+1+m1);
	sort(q2+1,q2+1+m2);
	int now = 0;
	//puts("");
	for (int i = 1;i <= m1;++i) {
		bool flag = 0;
		for (int j = 1;j <= now;++j) {
			if (q1[i].first > t[j]) {
				//printf("%d %d\n",j,i);
				t[j] = q1[i].second;
				buc1[j]++;
				flag = 1;
				break;
			}
		}
		if (!flag) {
			buc1[++now]++;
			t[now] = q1[i].second;
		}
		//printf("%d ",now);
	}
	memset(t,0,sizeof t);
	now = 0;
	for (int i = 1;i <= m2;++i) {
		bool flag = 0;
		for (int j = 1;j <= now;++j) {
			if (q2[i].first > t[j]) {
				t[j] = q2[i].second;
				buc2[j]++;
				flag = 1;
				break;
			}
		}
		if (!flag) {
			buc2[++now]++;
			t[now] = q2[i].second;
		}
		//for (int j = 1;j <= now;++j) printf("%d ",t[j]);
		//puts("");
		//printf("%d ",now);
	}
	for (int i = 1;i <= n;++i) {
		buc1[i] += buc1[i-1];
		buc2[i] += buc2[i-1];
	}
	int ans = 0;
	for (int i = 0;i <= n;++i) {
		//printf("%d %d\n",buc1[i],buc2[n-i]);
		ans = max(ans,buc1[i]+buc2[n-i]);
	}
	printf("%d\n",ans);
	return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...