校门外的树,允许较大l解法,C++版

http://pkuic.openjudge.cn/hw05/8/

#include <iostream>
using namespace std;
int main()
{
    int l, m;
    cin >> l >> m;
    int a[2][m] = {0};
    int k = 0;
    for (int i = 0; i < m; i++)
    {
        cin >> a[0][i] >> a[1][i];
        if (a[0][i] > a[1][i])
            swap(a[0][i], a[1][i]);//防止输入数据反向
        if (a[1][i] > l)
            a[1][i] = l;//忽略掉右侧超过l的部分
        if (a[0][i] > l)
        {
            i--;
            m--;
        }//忽略掉左侧超过l的输入
    }
    for (int i = 0; i < m; i++)
    {
        for (int j = i + 1; j < m; j++)
        {
            if (a[0][i] <= a[1][j] && a[0][j] <= a[1][i])
            {
                a[0][i] = min(a[0][i], a[0][j]);
                a[1][i] = max(a[1][i], a[1][j]);
                swap(a[0][j], a[0][m - 1]);
                swap(a[1][j], a[1][m - 1]);
                m--;
                j=i;
            }
        }
    }//合并重复砍掉的树
    for (int i = 0; i < m; i++)
    {
        k += (a[1][i] - a[0][i] + 1);
    }//计算砍掉的数
    l = l - k + 1;
    cout << l << endl;
    return 0;
}
发布日期:
分类:C++