原题链接
题意简述
有一条公路上有 \(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;//华丽的结束
}
标签:P9515,return,READ,POS,int,MAXR,洛谷,时刻,杂题
From: https://www.cnblogs.com/wangmarui/p/17852448.html