题目要求为下:第一行是一个整数n (1<n<10000)表示共有n个活动申请。 随后的n行,每行有两个正整数Bi, Ei (0<Bi<Ei<10000),分别表示第i个活动的起始与结束时间,即表示第i个活动申请占用礼堂的时间段为[Bi,Ei]。 输出格式: 输出最多能够安排的活动数目。#include <iostream> using namespace std; //定义结构体,储存每个 struct act{ int begin; int end; int time; }; int main(){ int n; int temp_end=0; int sum=1; struct act a[10010]; cin>>n; int i,j; for(i=0;i<n;i++){ cin>>a[i].begin>>a[i].end; a[i].time=a[i].end-a[i].begin; } //排序 for(i=0;i<n-1;i++){ for(j=0;j<n-i-1;j++){ if(a[j].begin>a[j+1].begin){ struct act temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } if(a[j].begin==a[j+1].begin){ if(a[j].time>a[j+1].time){ struct act temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } } temp_end=a[0].end; for(i=0;i<n-1;i++){ if(a[i+1].begin>a[i].end){ sum++; } } cout<<sum; }请你帮我修改优化代码
时间: 2024-03-05 09:50:31 浏览: 18
以下是优化后的代码:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
//定义结构体,储存每个活动的起始时间和结束时间
struct act{
int begin;
int end;
};
//按照活动结束时间从早到晚排序
bool cmp(act a,act b){
return a.end<b.end;
}
int main(){
int n;
cin>>n;
act a[10010];
int i,j,sum=0;
for(i=0;i<n;i++){
cin>>a[i].begin>>a[i].end;
}
sort(a,a+n,cmp); //排序
int temp_end=0;
for(i=0;i<n;i++){
if(a[i].begin>=temp_end){ //如果当前活动的开始时间晚于等于前一个活动的结束时间
sum++; //可以安排,计数器加1
temp_end=a[i].end; //更新前一个活动的结束时间
}
}
cout<<sum;
return 0;
}
```
优化说明:
1. 去掉了结构体中的 `time` 成员变量,因为不需要计算每个活动占用礼堂的时间。
2. 按照活动结束时间从早到晚排序,这样可以保证每次安排活动时,当前活动的结束时间一定是前面已经安排的活动中最早的。
3. 在循环中,仅需判断当前活动的开始时间是否晚于等于前一个活动的结束时间,如果是,则可以安排,计数器加1,并更新前一个活动的结束时间。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)