2019 笔试 学硕

/**
 * https://wenku.baidu.com/view/a0ca0e8ea0116c175f0e4816.html
某教学大楼一层有n个教室，从左到右依次编号为1、2、…、n。
 现在要把一些课桌从某些教室搬到另外一些教室，每张桌子都是从编号较小的教室搬到编号较大的教室，
 每一趟，都是从左到右走，搬完一张课桌后，可以继续从当前位置或往右走搬另一张桌子。
 输入数据：先输入n、m，然后紧接着m行输入这m张要搬课桌的起始教室和目标教室。输出数据：最少需要跑几趟。

 [网上题解]贪心算法，把课桌按起点从小到大排序，每次都是搬离当前位置最近的课桌。
 自己首先想到按终点从小到大排序 ？？是否正确？？
 动态规划 回溯法 解决此类问题可以么？
搬桌子问题
Sample Input
10 5
1 3
3 9
4 6
6 10
7 8
Sample Output
3

10 5
3 9
1 3
6 10
4 6
7 8


针对网上改动

 *
*/



//#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
struct Weizhi{
    int start;
    int end;
    //可以放些构造函数
    Weizhi():start(0),end(0){}
    Weizhi(int s,int e):start(s),end(e){}
};


void mysort(Weizhi a[],int n){
    for(int i=0;i<n;i++){
        for(int j = 0;j<n-i-1;++j){
            if(a[j].start > a[j+1].start){
                int temp = a[j].start;
                a[j].start = a[j+1].start;
                a[j+1].start = temp;
            }
        }
    }
}

bool cmp(Weizhi &c,Weizhi &b){
    return c.start < b.start;
}
int main(){
    Weizhi a[100];//换为向量也行 暂时不换了  否则需要把used也相应的替换  todo 后续测试替换为向量
//    vector<Weizhi> a;
    int i,j;
    int n,m,ans,num,temp;
    int used[100] = {0};
    scanf("%d%d",&m,&n);
    for(i=0;i<n;++i){
        scanf("%d%d",&a[i].start,&a[i].end);
    }
//    mysort(a,n); //ok
//    sort(a,n,cmp); // no matching function for call to 'sort'
        // vector -- sort(intervals.begin(),intervals.end(),cmp);
//    sort(a,a+n,cmp);
    sort(a,a+n,cmp);
    ans = 0;

    num = 0;
    while(num < n){
        temp = 0;
        for(i=0;i<n;++i){
            if(used[i]==0 && a[i].start>=temp){
                temp = a[i].end;
                used[i] = 1;
                num++;
            }
        }
        ans++;
    }

    printf("%d\n",ans);
}

杭电 1050 OJ 也有个搬桌子问题  todo