为什么三组样例都过了,洛谷数据保灵
查看原帖
为什么三组样例都过了,洛谷数据保灵
347839
Daniel_7216楼主2021/10/24 10:19

RT,我的做法是 O(n2logn)O(n^2logn),为什么全部都是 WA+TLE

//SN-00129 �����  ������һ�з�У 
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int N, n, m1, m2, L, R, sum, cnt1, cnt2, ans1[100001], ans2[100001];
struct plane1{
	int l, r;
}a[100001];
bool cmp(plane1 a, plane1 b){
	return a.l < b.l;
}
struct plane2{
	int l, r;
	bool operator < (const plane2 &x) const{
		return r >  x.r;
	}
}dlr;
priority_queue <plane2> q1, q2;
void change1(int i){
	dlr = q1.top();
	if (a[i].l > dlr.r){
		q1.pop();
		dlr.l = a[i].l;
		dlr.r = a[i].r;
		cnt1++;
		q1.push(dlr);
	}else{
		if (sum < n){
			sum++;
			dlr.l = a[i].l;
			dlr.r = a[i].r;
			cnt1++;
			q1.push(dlr);				
		}
	}
}
void update1(){
	while (!q1.empty()) q1.pop();
	sum = 0;
	dlr.l = a[1].l;
	dlr.r = a[1].r;
	cnt1++;
	sum++;
	q1.push(dlr); 
}
void change2(int i){
	dlr = q2.top();
	if (a[i].l > dlr.r){
		q2.pop();
		dlr.l = a[i].l;
		dlr.r = a[i].r;
		cnt2++;
		q2.push(dlr);
	}else{
		if (sum < n){
			sum++;
			dlr.l = a[i].l;
			dlr.r = a[i].r;
			cnt2++;
			q2.push(dlr);				
		}
	}
}
void update2(){
	while (!q2.empty()) q2.pop();
	sum = 0;
	dlr.l = a[1].l;
	dlr.r = a[1].r;
	cnt2++;
	sum++;
	q2.push(dlr); 
}
int main(){
	//freopen("airport.in", "r", stdin);
	//freopen("airport.out", "w", stdout);
	scanf("%d%d%d", &N, &m1, &m2);
	for (int i = 1; i <= m1; i++){
		scanf("%d%d", &a[i].l, &a[i].r);
	}
	sort(a + 1, a + 1 + m1, cmp);
	for (n = 1; n <= N; n++){
		cnt1 = 0;
		update1();
		for (int i = 2; i <= m1; i++){
			change1(i);
		}
		ans1[n] = cnt1;
		//printf("%d\n", cnt1);
	}
	for (int i = 1; i <= m2; i++){
		scanf("%d%d", &a[i].l, &a[i].r);
	}
	sort(a + 1, a + 1 + m2, cmp);
	for (n = 1; n <= N; n++){
		cnt2 = 0;
		update2();
		for (int i = 2; i <= m1; i++){
			change2(i);
		}
		ans2[n] = cnt2;
		//printf("%d\n", cnt2);
	}
	int ans = -1;
	for (int i = 0; i <= N; i++){
		ans = max(ans, ans1[i] + ans2[N - i]);
		//printf("%d %d\n", cnt1[i], cnt2[i - 1]);
	}
	printf("%d", ans);
	return 0;
}

救救孩子吧,我还年轻,不想AFO

2021/10/24 10:19
加载中...