34-语言入门-34-房间安排

题目地址： http://acm.nyist.net/JudgeOnline/problem.php?pid=168 

 

描述
2010年上海世界博览会(Expo2010),是第41届世界博览会。于2010年5月1日至10月31日期间，在中国上海市举行。本次世博会也是由中国举办的首届世界博览会。上海世博会以“城市，让生活更美好”(Better City,Better Life)为主题，将充分探索21世纪城市生活。
这次世博会总投资达450亿人民币，创造了世界博览会史上的最大规模记录。吸引200个国家和国际组织参展。预计有7000万人次的参观者。
为了更好地接待在这期间来自世界各地的参观者，如何合理安排各宾馆的住房问题提到了日程。组委会已接到了大量的客户住宿定单，每张定单的内容包括要住宿的房间数，开始住宿时间和要住的天数。为了便于整个城市各宾馆的管理，组委会希望对这些定单进行安排，目的是用尽可能少的房间来满足这些定单，以便空出更多的房间用于安排流动游客。
组委会请求DR.Kong来完成这个任务，对这些定单进行合理安排，使得满足这些定单要求的房间数最少。
假设：某个定单上的游客一旦被安排到某房间，在他预定住宿的期间内是不换房间的。为了简化描述，定单上的开始住宿时间为距离现在的第几天。例如，定单为（10，30，5）表示游客要求使用10个房间，第30天开始连住5天。

输入
第一行：T 表示有T组测试数据
每组测试数据第一行：N 表示定单数
每组测试数据接下来有N行，每行有三个整数 A B C 表示房间数，开始住宿时间和天数
1<=T<=100
1<=N<=10000 1<=A<=10 1<=B<=180 1<=c<=10
输出
输出一个整数，为满足所有定单要求的最少房间数。
样例输入
1
3
3 10 4
4 9 3
3 12 6
样例输出

7

 

 

笨办法：

#include <stdio.h>
#include <stdlib.h>

typedef struct _Order
{
    //房间数目
    int roomNum;
    //开始时间
    int startTime;
    //总天数
    int totalDate;
    //临时剩余房间
    int tmpRoomNum;
}Order;

//处理每组数据
void handlerData();

int main()
{
    int readLen = 0;
    scanf("%d",&readLen);
    getchar();
   
    while (readLen > 0)
    {
        handlerData();
       
        --readLen;
    }
   
    return 0;
}

void printResult(Order *arr,int len)
{
    printf(" -------------- ");
    int i=0;
    for (; i<len; ++i)
    {
        printf("    %d %d %d ",arr[i].roomNum,arr[i].startTime,arr[i].totalDate);
    }
    printf("-------------- ");
}

//处理每组数据
void handlerData()
{
    int readLen = 0;
    scanf("%d",&readLen);
    getchar();
   
    Order *orderLst = (Order*)malloc(sizeof(Order)*readLen);
    int arr_len = readLen;
   
    int index = 0;
    while (readLen > 0)
    {
        scanf("%d %d %d",&orderLst[index].roomNum,&orderLst[index].startTime,&orderLst[index].totalDate);
        getchar();
        orderLst[index].tmpRoomNum = orderLst[index].roomNum;
        ++index;
       
        --readLen;
    }
   
    //printResult(orderLst,arr_len);
   
    //排序
    int i=0;
    for (; i<arr_len-1; ++i)
    {
        int minIndex = i;
        int j = i+1;
        for (; j<arr_len; ++j)
        {
            if (orderLst[minIndex].startTime > orderLst[j].startTime)
            {
                minIndex = j;
            }
        }
       
        if(minIndex != i)
        {
            Order tmpOrder = orderLst[i];
            orderLst[i] = orderLst[minIndex];
            orderLst[minIndex] = tmpOrder;
        }
    }
   
    //处理数据
    i=0;
    for (; i<arr_len-1; ++i)
    {
        if (orderLst[i].roomNum>0 && orderLst[i].tmpRoomNum>0)
        {
            int j = i+1;
            int nextStart = orderLst[i].startTime+orderLst[i].totalDate;
            for (; j<arr_len; ++j)
            {
                if (nextStart <= orderLst[j].startTime && orderLst[j].roomNum>0)
                {
                    if (orderLst[j].roomNum > orderLst[i].roomNum)
                    {
                        orderLst[i].tmpRoomNum = 0;
                        orderLst[j].roomNum -= orderLst[i].roomNum;
                        orderLst[j].tmpRoomNum = orderLst[j].roomNum;
                        break;
                    }
                    else
                    {
                        orderLst[i].tmpRoomNum -= orderLst[j].roomNum;
                        orderLst[j].roomNum = orderLst[j].tmpRoomNum = 0;
                    }
                }
            }
        }
    }
   
    //printResult(orderLst,arr_len);
   
    //计算总数量
    int sum = 0;
    i=0;
    for (; i<arr_len; ++i)
    {
        sum += orderLst[i].roomNum;
    }
   
    //输出结果
    printf("%d ",sum);
   
    free(orderLst);
    orderLst = NULL;
}

首先考虑数据如何存储，然后考虑数据如何处理解决问题。

该种思路在对数据处理过程种，花费时间过多。

 

 

另一种思路，就是要找到数据的规律，如果将开始时间作为横轴，房间数作为Y轴，形成一个坐标系，每一看成一个矩形条数据，开始时间是X坐标，预定房间的时间是矩形的长，预定房间数是矩形的高。则实例中的三条数据可以形成类似下图：

矩形重叠部分最大值，为最大订约房间数。

 

代码：

#include <stdio.h>

//最大订单数
#define ORDER_LEN  200

//处理每组数据
static void handlerData();

int main()
{
    int readLen = 0;
    scanf("%d",&readLen);
    getchar();
   
    while (readLen > 0)
    {
        handlerData();
       
        --readLen;
    }
   
    return 0;
}

//处理每组数据
static void handlerData()
{
    int readLen = 0;
    scanf("%d",&readLen);
    getchar();
   
    int orderArr[ORDER_LEN] = {0};
   
    while (readLen > 0)
    {
        int homeNum = 0;
        int startTime = 0;
        int dayNum = 0;
       
        scanf("%d %d %d",&homeNum,&startTime,&dayNum);
        getchar();
       
        int j = startTime;
        for (; j<startTime+dayNum; ++j)
        {
            orderArr[j] += homeNum;
        }
       
        --readLen;
    }
   
    int i = 1; //1-180
    int maxRoom = 0;
    for (; i<ORDER_LEN; ++i)
    {
        if(maxRoom < orderArr[i])
        {
            maxRoom = orderArr[i];
        }
    }
   
    printf("%d ",maxRoom);
}