poj-2376 Cleaning Shifts

2016年07月13日 |

acm

| acm

• 题目：
• 代码：
• 解析&吐槽：

题目：

Cleaning Shifts
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 17287 Accepted: 4403

Description
Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first being shift 1 and the last being shift T.

Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval.

Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print -1.

Input
\\\* Line 1: Two space-separated integers: N and T

\\\* Lines 2..N+1: Each line contains the start and end times of the interval during which a cow can work. A cow starts work at the start time and finishes after the end time.

Output
\\\* Line 1: The minimum number of cows Farmer John needs to hire or -1 if it is not possible to assign a cow to each shift.

Sample Input

3 10
1 7
3 6
6 10

Sample Output

2

Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.

INPUT DETAILS:

There are 3 cows and 10 shifts. Cow #1 can work shifts 1..7, cow #2 can work shifts 3..6, and cow #3 can work shifts 6..10.

OUTPUT DETAILS:

By selecting cows #1 and #3, all shifts are covered. There is no way to cover all the shifts using fewer than 2 cows.

代码：

// oj.cpp : 定义控制台应用程序的入口点。
//
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <numeric>
#include <cstring>
#include <map>
#include <set>
#include <utility>
#include <map>
#include <list>
#include <queue>
#include <functional>
#include <bitset>
#include <stack>
#include <deque>
#include <limits>
#include <cmath>

using namespace std;

typedef pair<int, int> P;
P L[25010];
bool cmp(const P& l, const P& r)
{
    if (l.first == r.first)
        return l.second > r.second;
    else
        return l.first < r.first;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, T;
    while (cin >> N >> T)
    {
        for (int i = 0;i < N;++i)
        {
            cin >> L[i].first >> L[i].second;
            //if (L[i].first > L[i].second)
            //	swap(L[i].first, L[i].second);
        }

        sort(L, L + N/*, cmp*/);

        int cnt = 1;
        if (L[0].first > 1)
        {
            cnt = -1;
        }
        else
        {
            int start = 1;
            int end = L[0].second;
            int i = 1;

            while (end < T)
            {
                if (i >= N)
                {
                    cnt = -1;
                    break;
                }

                if (L[i].second <= end)
                {
                    ++i;
                    continue;
                }

                if (L[i].first <= start&&L[i].second > end)
                {
                    end = L[i].second;
                    ++i;
                    continue;
                }

                if (L[i].first > end + 1)
                {
                    cnt = -1;
                    break;
                }

                ++cnt;
                start = end + 1;
                end = L[i].second;
                ++i;
            }
        }

        cout << cnt << endl;
    }
}

解析&吐槽：

每一个节点都可以覆盖某个区间，选出最少的节点来覆盖指定的区间。明显的贪婪算法，但是有不少坑点。

首先，尽管题目没说，但是题目是有多组数据的！其次，如果上一个节点覆盖的区间是 i-j，下一个节点覆盖的区间可以从 j+1 开始。 最后，要覆盖的区间是从 1 开始，到 T 结束的。

在做题的时候也要注意几方面：题目可能会有无法覆盖整个区间的情况（无解），对于排过序的区间数据，如果第一个数据的区间左端点 大于 1 或者最后一个数据的右端点小于 T；就无解，如果遍历的时候不是以数据的索引作为循环变量的话，一定要注意判断是否达到的 最后一个数据。还要注意如果贪心策略是选择左端点不大于上一个选择的右端点（加一）的长度最大的区间，我的方法是如果判断下一 个数据比上一个更好的话，就更新记录的右端点，不自增计数。这样的话，排序的时候只需要考虑左端点，右端点不用管。我这里用 pair 来保存数据，它的比较函数会先比较 first 元素，在相等时再比较 second。我写的那个比较函数实际上是用不到的。还有我看到 有很多题解都会考虑输入数据中第一个比第二个大的情况，实测这个是不需要判断的，我注释掉了那段代码仍然可以 ac（见第 45 行）。