15pts求思路指正哪错了
查看原帖
15pts求思路指正哪错了
726735
Sirius_M楼主2022/10/17 19:20

额马蜂有点奇怪请见谅,主要是想改暂时还没改过来

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m1, m2;
struct Stu{
	int da, li;
}a[N], b[N];//表示飞机
struct{
	int li, ch;
}aa[N], bb[N];//表示廊桥
bool cmp(Stu x, Stu y){return x.da < y.da;}
int sum1 = 0, sum2 = 0;//需要几个廊桥 
int main(){
	cin>> n >> m1 >> m2 ;
	for(int i = 1;i <= m1; i ++ ) cin>> a[i].da >> a[i].li;
	for(int i = 1;i <= m2; i ++ ) cin>> b[i].da >> b[i].li;
	sort(a + 1, a + m1 + 1, cmp);
	sort(b + 1, b + m2 + 1, cmp);
	aa[1].li = a[1].li;
	aa[1].ch = 1;
	sum1 = 1;
	int minn = a[1].li;//最早离开时间 
	for(int i = 2; i <= m1; i ++ ){
		int flag = 1;
		if(a[i].da <= minn){//需要分配一个新的廊桥
			aa[++ sum1 ].ch = 1;//该廊桥一共停了几个飞机了
			aa[sum1].li = a[i].li;
			minn = min(minn, a[i].li);
			continue;
		}
		for(int j=1;j<=sum1;j++)//找第一个能符合的廊桥
			if(aa[j].li<=a[i].da){
				aa[j].li=a[i].li;
				flag=0;//不用开新的廊桥了
				aa[j].ch++;//本廊桥多了一个飞机的停放
				break;
			}
	}
	bb[1].li=b[1].li;
	bb[1].ch=1;
	sum2=1;
	minn=b[1].li;
	for(int i=2;i<=m2;i++){
		int flag=1;
		if(b[i].da<=minn)
		{
			bb[++sum2].ch=1;
			bb[sum2].li=b[i].li;
			minn=min(minn,b[i].li);
			continue;
		}
		for(int j=1;j<=sum2;j++)
			if(bb[j].li<=b[i].da){
				bb[j].li=b[i].li;
				flag=0;
				bb[j].ch++;
				break;
			}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		aa[i].ch+=aa[i-1].ch;//当有i个廊桥时可以放几个飞机
		bb[i].ch+=bb[i-1].ch;
	}
	for(int i=0;i<=n;i++) ans=max(ans,aa[i].ch+bb[n-i].ch);//枚举廊桥的分配
	cout<<ans;
}

这个是15分代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m1, m2;
struct Stu{
	int da, li;
}a[N], b[N];//表示飞机
struct{
	int li, ch;
}aa[N], bb[N];//表示廊桥
bool cmp(Stu x, Stu y){return x.da < y.da;}
int sum1 = 0, sum2 = 0;//需要几个廊桥 
int main(){
	cin>> n >> m1 >> m2 ;
	for(int i = 1;i <= m1; i ++ ) cin>> a[i].da >> a[i].li;
	for(int i = 1;i <= m2; i ++ ) cin>> b[i].da >> b[i].li;
	sort(a + 1, a + m1 + 1, cmp);
	sort(b + 1, b + m2 + 1, cmp);
	aa[1].li = a[1].li;
	aa[1].ch = 1;
	sum1 = 1;
	int minn = a[1].li;//最早离开时间 
	for(int i = 2; i <= m1; i ++ ){
		int flag = 1;
		if(a[i].da <= minn){//需要分配一个新的廊桥
			aa[++ sum1 ].ch = 1;//该廊桥一共停了几个飞机了
			aa[sum1].li = a[i].li;
			minn = min(minn, a[i].li);
			continue;
		}
		for(int j=1;j<=sum1;j++)//找第一个能符合的廊桥
			if(aa[j].li<=a[i].da){
				aa[j].li=a[i].li;
				flag=0;//不用开新的廊桥了
				aa[j].ch++;//本廊桥多了一个飞机的停放
				break;
			}
		if(flag){//如果没有开新廊桥
			aa[++sum1].ch=1;//找了一圈都没有合适的
			aa[sum1].li=a[i].li;
		}
		minn=min(minn,a[i].li);
	}
	bb[1].li=b[1].li;
	bb[1].ch=1;
	sum2=1;
	minn=b[1].li;
	for(int i=2;i<=m2;i++){
		int flag=1;
		if(b[i].da<minn)
		{
			bb[++sum2].ch=1;
			bb[sum2].li=b[i].li;
			minn=min(minn,b[i].li);
			continue;
		}
		for(int j=1;j<=sum2;j++)
			if(bb[j].li<=b[i].da){
				bb[j].li=b[i].li;
				flag=0;
				bb[j].ch++;
				break;
			}
		if(flag){
			bb[++sum2].ch=1;
			bb[sum2].li=b[i].li;
		}
		minn=min(minn,b[i].li);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		aa[i].ch+=aa[i-1].ch;//当有i个廊桥时可以放几个飞机
		bb[i].ch+=bb[i-1].ch;
	}
	for(int i=0;i<=n;i++) ans=max(ans,aa[i].ch+bb[n-i].ch);//枚举廊桥的分配
	cout<<ans;
}

这个代码是AC的。区别在于,两份代码都特判了一下如果这个飞机到达的时间比之前所有飞机最早离开的还要早,那么直接开一个廊桥。问题在于我认为这么特判之后这种需要开新廊桥的情况就处理完了(即代码1),不知道存在哪种可能没被考虑到?

2022/10/17 19:20
加载中...