求助暴力部分分有WA
查看原帖
求助暴力部分分有WA
929147
Davidkroos楼主2023/10/6 11:36
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n , m1 , m2;
int a1[MAXN] , a2[MAXN] , b1[MAXN] , b2[MAXN] , v1[MAXN] , v2[MAXN] , flag1[MAXN] , flag2[MAXN];
int num1[MAXN] , num2[MAXN];
int sum[MAXN];
signed main(){
//	freopen("airport.in" , "r" , stdin);
//	freopen("airport.out" , "w" , stdout);
	cin >> n >> m1 >> m2;
	for(int i = 1;i <= m1; i ++){
		cin >> a1[i] >> b1[i];
		v1[i] = b1[i] - a1[i];
	}
	for(int i = 1;i <= m2; i ++){
		cin >> a2[i] >> b2[i];
		v2[i] = b2[i] - a2[i];
	}
	if(n >= m1 + m2){
		cout << n;
		return 0;
	}
	int k1 = 0;
	for(int i = 1;i <= m1; i ++){
		if(flag1[i] == 1) continue;
		k1 ++;
		int end = b1[i];
		flag1[i] = 1;
		num1[k1] ++;
		for(int j = 1;j <= m1;j ++){
			if(flag1[j] == 1) continue;
			if(a1[j] > end){
				end = b1[j];
				num1[k1] ++;
				flag1[j] = 1;
			}
		}
	}
//	for(int i = 1;i <= k1; i ++){
//		cout << num1[i] << " ";
//	}
	int k2 = 0;
	for(int i = 1;i <= m2; i ++){
		if(flag2[i] == 1) continue;
		k2 ++;
		int end = b2[i];
		flag2[i] = 1;
		num2[k2] ++;
		for(int j = 1;j <= m2;j ++){
			if(flag2[j] == 1) continue;
			if(a2[j] > end){
				end = b2[j];
				num2[k2] ++;
				flag2[j] = 1;
			}
		}
	}
//	for(int i = 1;i <= k2; i ++){
//		cout << num2[i] << " ";
//	}
	for(int i = 1;i <= k1; i ++){
		sum[i] = num1[i];
	}
	for(int i = 1;i <= k1; i ++){
		sum[i + k1] = num2[i];
	}
	sort(sum + 1, sum + k1 + k2 + 1);
	int ans = 0 , i = k1 + k2;
	while(n --){
		ans += sum[i];
		i --;
	}
	cout << ans;
}
//3 5 4
//1 5
//3 8 
//6 10
//9 14
//13 18
//2 11
//4 15
//7 17
//12 16

//2 4 6 
//20 30
//40 50
//21 22
//41 42
//1 19 
//2 18
//3 4
//5 6
//7 8
//9 10
2023/10/6 11:36
加载中...