題目描述

現(xiàn)在各大oj上有n個比賽，每個比賽的開始、結(jié)束的時間點是知道的。

yyy認為，參加越多的比賽，noip就能考的越好（假的）

所以，他想知道他最多能參加幾個比賽。

由于yyy是蒟蒻，如果要參加一個比賽必須善始善終，而且不能同時參加2個及以上的比賽。

輸入輸出格式

輸入格式：

第一行是一個整數(shù)n ，接下來n行每行是2個正整數(shù)ai,bi(ai<bi)，表示比賽開始、結(jié)束的時間。

輸出格式：

一個整數(shù)最多參加的比賽數(shù)目。

輸入輸出樣例

輸入樣例#1：

3
0 2
2 4
1 3

輸出樣例#1：

2

思路：將每一場比賽以結(jié)束時間排一次序，得到一個順序的結(jié)構(gòu)體數(shù)組，存儲最前面一節(jié)課的下課時間，然后以結(jié)束時間為準，在這相同結(jié)束時間比賽中下，如果有比賽的開始時間小于等于記錄的結(jié)束時間，直接參加比賽，然后計數(shù)，最后輸出總次數(shù)。

源代碼

#include<iostream> #include<algorithm> using namespace std; struct game{//結(jié)構(gòu)體int begin;int end; }arr[100000]; bool cmp(game a,game b){//排序因子return a.end<b.end;//按比賽結(jié)束時間升序 } int main() {int n,total=0;int temp;int i;cin>>n;for(i=1;i<=n;i++) cin>>arr[i].begin>>arr[i].end;//輸入每場比賽開始、結(jié)束時間sort(arr+1,arr+1+n,cmp);//升序排序temp=0;//令temp為上一場比賽的結(jié)束時間for(i=1;i<=n;i++)//對所有比賽進行遍歷{if(temp<=arr[i].begin)//當結(jié)束時間小于下一場比賽的開始時間時，進行下一場比賽{temp=arr[i].end;//記錄新一場的結(jié)束時間total++;//參加場數(shù)+1}} cout<<total<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的凌乱的yyy（洛谷-P1803）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。