51Nod－1631－小鲨魚在51Nod國小

ACM模版

描述

題解

暴力解題就能通過，資料比較水，感覺我的代碼有些麻煩，有很大的優化空間。

這裡要說的是，其實年月日可以轉化為一個獨有的序号轉存，這個序号依然保持原來日期的對比關系。

比如說，将2001年1月1日存為：

20010101，（2001*10000 + 1 * 100 + 1）

，這樣子，兩個日期間的對比關系用此序号對比依然成立。

也可以使用

<set>

集合優化。

代碼

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN =  + ;

struct task
{
    int y0, m0, d0;
    int y1, m1, d1;
    int number;
} Task[MAXN];

int res[MAXN];  //  存儲任務序号 res[0] 存儲任務個數

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = ;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret *  + (c - '0'), c = getchar();
    }
    return ;
}

bool cmp(task a, task b)
{
    return a.number < b.number;
}

int main(int argc, const char * argv[])
{
//    freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    int n;
    scan_d(n);

    int key = ;
    int y0, y1, m0, m1, d0, d1;
    int number;
    for (int i = ; i < n; i++)
    {
        scan_d(y0);
        scan_d(m0);
        scan_d(d0);
        scan_d(y1);
        scan_d(m1);
        scan_d(d1);
        scan_d(number);
        if ((y0 == y1 && m0 == m1) || (y0 == y1 && m0 == m1 -  && d0 > d1) || (y0 == y1 -  && m0 ==  && m1 ==  && d0 > d1))
        {
            continue;
        }
        Task[key].y0 = y0;
        Task[key].m0 = m0;
        Task[key].d0 = d0;
        Task[key].y1 = y1;
        Task[key].m1 = m1;
        Task[key].d1 = d1;
        Task[key++].number = number;
    }
    sort(Task, Task + key, cmp);

    int q;
    scan_d(q);

    int y, m, d;
    for (int i = ; i < q; i++)
    {
        res[] = ;
        scan_d(y);
        scan_d(m);
        scan_d(d);
        for (int i = ; i < key; i++)
        {
            if (y >= Task[i].y0 && y <= Task[i].y1)
            {
                if ((y == Task[i].y0 && m < Task[i].m0) || (y == Task[i].y0 && m == Task[i].m0 && d < Task[i].d0) || (y == Task[i].y1 && m > Task[i].m1) || (y == Task[i].y1 && m == Task[i].m1 && d > Task[i].d1))
                {
                    continue;
                }
                res[]++;
                res[res[]] = Task[i].number;
            }
        }
        for (int i = ; i < res[]; i++)
        {
            printf("%d ", res[i]);
        }
        printf("%d\n", res[res[]]);
    }

    return ;
}