自动搬运

查看原文

来自洛谷，原作者为

	wmrqwq 会登顶的。

搬运于2025-08-24 22:49:06，当前版本为作者最后更新于2023-08-11 18:58:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

原题链接

P9515 「JOC-1A」限时签到

题意简述

有一条公路上有 $n$ 个商店，每个商店分别在不同的时刻开放，求如何在 $t$ 时刻之前到达 $f$ 点并且到达最多开放的商店的数量，特别的，一个时刻只能走一格。

解题思路

这一道题是一道贪心题。首先，因为要在 $t$ 时刻之前到达 $f$ 点，所以我们可以直接理解为要在 $t-f$ 的时刻到达原点。所以，为了避免走过重复的路径，我们可以到一定的时刻直接从原点走到 $f$ 点，只需要判断 $x_i-a_i$ 是否大于 $t$ 即可，如果成立，就将 $ans$ 增加 $1$，最后直接输出 $ans$ 即可。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define QwQ return 0;
long long n,t,f,a,b,ans;
namespace IO {//快读
    const int MAXR = 100000;
    char _READ_[MAXR], _PRINT_[MAXR];
    int _READ_POS_, _PRINT_POS_, _READ_LEN_;
    inline char readc() {
    #ifndef ONLINE_JUDGE
        return getchar();
    #endif
        if (!_READ_POS_) {
            if (feof(stdin)) return -1;
            _READ_LEN_ = fread(_READ_, 1, MAXR, stdin);
        }
        char c = _READ_[_READ_POS_++];
        if (_READ_POS_ == _READ_LEN_) _READ_POS_ = 0;
        return c;
    }
    template<typename T> inline int read(T &x) {
        x = 0; register int flag = 1, c;
        while (((c = readc()) < '0' || c > '9') && c != '-')
            if (c < 0) return -1;
        if (c == '-') flag = -1; else x = c - '0';
        while ((c = readc()) >= '0' && c <= '9') x = x * 10 - '0' + c;
        x *= flag; return 0;
    }
}
int main()
{
	cin>>n>>t>>f;
	t-=f;//贪心结论1
	for(int i=0;i<n;i++)
	{
		IO::read(a);
		IO::read(b);//注意，这里为了避免MLE，所以直接将数组转化为变量
		if(b-a<=t)	//贪心结论2
			ans++;//如果符合，将ans增加1
	}
	cout<<ans;//输出答案
	QwQ;//华丽的结束
}