自动搬运

查看原文

来自洛谷，原作者为

	PTC06 None

搬运于2025-08-24 21:40:25，当前版本为作者最后更新于2016-11-03 21:24:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

此题只要理解思路，就可以做出来的。只不过初次提交时有很多点RE。后来发现原因在于数组定义的不够大。=_=

思路如下：

首先，让我们从样例分析。样例是：

3 10 1 7 3 6 8 10 那么我的解题思路是：首先输入N和T，然后输入每头牛可以工作的时间是从哪个时间段到哪个时间段。那么我们用数组a来标记每头牛的时间段，我用数组a的下标来表示开始时间，而a[i]中的数就是牛的结束时间。

如图所示，a[1]是7， a[3]是6，a[8]是10. 注意，输入时需要去重，也就是当有两头或以上的牛的开始时间一样时，就需要判断哪头牛的结束时间更晚（也就是工作时间长的那头），把a中的元素更新。接下来，a的元素弄好了，也就到了重点了。这里需要定义两个变量——start和end，用处下面会讲。下面是部分程序。

    for (i=start+1;i<=end+1;i++)
    {
        if (temp<a[i]) temp=a[i];
    }

这里这条循环的作用是寻找下一个循环中的end，意思就是，在已经确定有牛在干活的时间段中（这个条件很重要，带来了很多便利，因为这样就不会产生有一些时间没有牛清洁的情况），继续寻找下一个该干活的牛（也就是结束时间最晚的那头）。注意这里从start+1开始，到end+1结束。加一是因为，这里的加一是因为，end+1表示已经有牛清洁的时间段的下1个时间段，如果这个时间有牛可以干活，也并不会产生没有牛清洁的情况。好了，这里解释完了，到下一个部分。下面是部分程序:

        if (temp<end+1)
        {
            cout<<-1;
            return 0;
        }

这里的判断是为了判断会不会出现题目中说的 “不可能”情况。也就是如果这一段中的最晚结束时间都还没有到需要清洁的时间，那么显然就不可能完成清洁了。好了，下一步，还是先上部分程序： start=end;

end=temp;

sum++;

这里就是很明显的更新了。把start变成原来的end，而下一轮的end又变成此时的最晚结束时间。

下面是AC程序。

#include<iostream>
#include<cstdio> 
using namespace std;
int n,m,i,t,t1,a[1000000],temp,start,end,sum;         //注意a需要定义到一百万，也就是T的范围。一开始脑抽定义了N的范围，也就是25000，结果一直RE找不出错。
int main()
{
    cin>>n>>m;
    for (i=1;i<=n;i++)
    {
        cin>>t>>t1;            //输入
        if (a[t]<t1) a[t]=t1;                       //标记每一个牛的开始和结束时间。
    }
    while (temp<m)            //凡是temp<m，也就是总共需要清洁的那t个时间段，就继续.
    {
        for (i=start+1;i<=end+1;i++)
        {
            if (temp<a[i]) temp=a[i];                 //如上面的解释，找结束时间最晚的那头。
        }
        if (temp<end+1)                       //判断是否不可能。
        {
            cout<<-1;
            return 0;
        }
        start=end;               //更新
        end=temp;
        sum++;
    }
    cout<<sum;
    return 0;
}