题目大意

有N (1 <= N <= 100,000)头奶牛在一个单人的超长跑道上慢跑，每头牛的起点位置都不同。由于是单人跑道，所有他们之间不能相互超越。当一头速度快的奶牛追上另外一头奶牛的时候，他必须降速成同等速度。我们把这些跑走同一个位置而且同等速度的牛看成一个小组。

请计算T (1 <= T <= 1,000,000,000)时间后，奶牛们将分为多少小组。

题解

定义两头牛“能单独追上”为：若跑道上只有这两头牛，则它们能否追上。牛i和牛j（j>i）将会位于同一小组当且仅当j是位于i前方牛群中第一个能被i单独追上的牛（注意：是【前方牛群】，而不是【前方的牛】）。因为j一定时，能追上j的i有多个，所以倒序枚举。

注意：如果要暴力对拍，暴力程序应当尽量简单。如果写暴力程序无法保证正确性，写暴力程序也不值了。

#include <cstdio>

#include <cstring>

using namespace std;

#define ll long long

const int MAX_COW = 100010;

ll N, T;

struct Cow

{

	ll Pos, V;

}_cows[MAX_COW];

int main()

{

	scanf("%lld%lld", &N, &T);

	for (int i = 1; i <= N; i++)

		scanf("%lld%lld", &_cows[i].Pos, &_cows[i].V);

	ll groupCnt = N;

	int p = N;

	for (int i = N - 1; i >= 1; i--)

	{

		if ((_cows[i].V - _cows[p].V)*T >= _cows[p].Pos - _cows[i].Pos)

			groupCnt--;

		else

			p = i;

	}

	printf("%lld\n", groupCnt);

	return 0;

}

巴特西

luogu3111 [USACO14DEC]牛慢跑Cow Jog_Sliver

题目大意

题解

最新文章

热门文章