贪心+结构体快排

客官°小女子只卖身不卖艺 2022-07-11 08:27 127阅读 0赞

活动选择问题  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
sdut 大学生艺术中心每天都有n个活动申请举办，但是为了举办更多的活动，必须要放弃一些活动，求出每天最多能举办多少活动。

Input  
输入包括多组输入，每组输入第一行为申请的活动数n(n<100)，从第2行到n+1行，每行两个数，是每个活动的开始时间b，结束时间e；

Output  
输出每天最多能举办的活动数。

Example Input  
12  
15 20  
15 19  
8 18  
10 15  
4 14  
6 12  
5 10  
2 9  
3 8  
0 7  
3 4  
1 3

Example Output  
5

Hint  
多组输入  
Author

#include <stdio.h>
    #include <stdlib.h>
    #define MAXN 104
    typedef struct node
    {
        int begin;
        int end;
        int flag;
    }st;
    int count;//定义全局计数变量
    st a[MAXN], b[MAXN];//定义全局结构体
    int cmp(const void *a, const void *b)
    {
        if(((st *)a)->end != ((st *)b)->end)
        {
            return (((st *)a)->end - ((st *)b)->end);//升序
        }
        else if(((st *)a)->end == ((st *)b)->end)
        {
            return (((st *)a)->flag - ((st *)b)->flag);//升序
        }
    }
    void build(int n)//结构体元素建立函数
    {
        int i;
        for(i = 0; i < n; i++)
        {
            scanf("%d %d", &a[i].begin, &a[i].end);
            a[i].flag = i;
        }
    }
    void judge(int n)//活动选择判断函数
    {
        int i, k;
        qsort(&a[0], n, sizeof(a[0]), cmp);//调用快排函数
        i = k = 0;
        b[0] = a[0];//b[0]初始化
        count += 1;//初始化变化
        for(i = 1; i < n; i++)
        {
            if(b[k].end <= a[i].begin)
            {
                b[++k] = a[i];
                count++;
            }
        }
    }
    int main()
    {
        int n;
        while(scanf("%d", &n) != EOF)
        {
            build(n);//调用元素建立函数
            count = 0;
            judge(n);//调用活动选择判断函数
            printf("%d\n", count);
        }
    
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 0ms
    Take Memory: 108KB
    Submit time: 2017-01-21 11:54:49
    ****************************************************/

introspection：1、多组输入  
2、count的初始化和初始化变化