UVA-10020 Minimal coverage

2016年07月25日 |

acm

| acm

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

题目：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=961

代码：

// oj.cpp : 定义控制台应用程序的入口点。
//

#include <iostream>
#include <limits>
#include <algorithm>
#include <numeric>
#include <string>
#include <utility>
#include <cstdlib>
#include <vector>
#include <sstream>
//#include <cstdio>

using namespace std;

typedef pair<int, int> P;
P L[100010];
int have[100010];

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

    int T;
    cin >> T;
    while (T--)
    {
        int endi = 0, m;
        cin >> m;
        while (cin >> L[endi].first >> L[endi].second && (L[endi].first || L[endi].second))
            ++endi;

        sort(L, L + endi);

        int haveend = 0, last = 0;
        for (int i=0;i < endi;++i)
        {
            if (L[i].first > last)
            {
                haveend = 0;
                break;
            }

            int maxleft = i;
            for (int j = i+1;j < endi&&L[j].first<=last;++j)
            {
                if (L[j].second >= L[maxleft].second)
                    maxleft = j;
            }

            i = maxleft;

            if (L[i].second < 0)
            {
                haveend = 0;
                break;
            }

            have[haveend++] = i;

            last = L[i].second;

            if (last >= m)
                break;
        }

        if (last < m)
        {
            cout << 0 << endl;
        }
        else
        {
            cout << haveend << endl;
            for (int i = 0;i < haveend;++i)
                cout << L[have[i]].first << ' ' << L[have[i]].second << endl;
        }
        if (T)
            cout << endl;
    }
}

解析&吐槽：

标准的区间覆盖问题，这道题还把情况变得容易了一些，左端点是固定的，只有右端点是变量 M。区间覆盖的教程参见：http://blog.sina.com.cn/s/blog_892cc2ff01013cn4.html