洛谷P2338 Bessie Slows Down S 题解

题目

题解

这道题其实蛮简单的，不知道为什么难度划到了提高+，个人觉得这难度大概就是普及左右。

具体说说怎么做吧，简单模拟一下即可，始终记录下当前的时间、位置和速度，每遇到一个失误更新一下，将遇到失误的时间和位置分别排序，然后双指针，找到下一个最近失误的时间和位置，直到所有的失误都结束，最后再将总时间加上剩下的路程/当前速度。

需要注意的是结果四舍五入。

代码

#include<iostream>

#include<algorithm>

using namespace std;

int t[10000], d[10000];

int num_t = 0, num_d = 0;

double len = 0;

double tt = 0;

int main()

{

	ios::sync_with_stdio(false);

	int n;

	char c;

	int sp = 1;

	cin >> n;

	for (int i = 0; i < n; i++)

	{

		cin >> c;

		if (c == 'D')

			cin >> d[num_d++];

		else

			cin >> t[num_t++];

	}

	sort(d, d + num_d);

	sort(t, t + num_t);

	int i = 0, j = 0;

	while (i < num_t && j < num_d)

	{

		double next = 1 / (double)sp * (t[i] - tt)+len;

		if (next < d[j])

		{

			tt = t[i++];

			len = next;

			sp++;

		}

		else if (next > d[j])

		{

			tt += (d[j] - len) * sp;

			len = d[j++];

			sp++;

		}

		else

		{

			tt = t[i++];

			len = d[j++];

			sp += 2;

		}

	}

	while (i < num_t)

	{

		len += 1 / (double)sp * (t[i] - tt);

		tt = t[i++];

		sp++;

	}

	while (j < num_d)

	{

		tt += (d[j] - len) * sp;

		len = d[j++];

		sp++;

	}

	tt += (1000 - len) * sp;

	cout << (int)(tt + 0.5);

	return 0;

}

巴特西

洛谷P2338 Bessie Slows Down S 题解

题目

题解

代码

最新文章

热门文章