[数据结构与算法]A - Bridge and Sheets

Time Limit: 2 sec / Memory Limit : 1024 MB

Score : 300300 points

Contest URL : https://atcoder.jp/contests/arc134

Problem Statement

Snuke bought a bridge of length LL. He decided to cover this bridge with blue tarps of length W each.

Below, a position on the bridge is represented by the distance from the left end of the bridge. When a tarp is placed so that its left end is at the position x (0≤x≤L?W, xx is real), it covers the range [x, x+W]. (Note that both ends are included.)

He has already placed N tarps. The left end of the i-th tarp is at the position ai?.

At least how many more tarps are needed to cover the bridge entirely? Here, the bridge is said to be covered entirely when, for any real number x between 0 and L (inclusive), there is a tarp that covers the position x.

Constraints

• All values in input are integers.
• 1≤N≤10^5
• 1≤W≤L≤10^18
• 0≤a1?<a2?<?<aN?≤L?W

Input

Input is given from Standard Input in the following format:

N L W
a1? ? aN?

Output

Print the minimum number of tarps needed to cover the bridge entirely.

Sample Input 1?

2 10 3
3 5

Sample Output 1?

2

• The bridge will be covered entirely by, for example, placing two tarps so that their left ends are at the positions?0?and?7.

Sample Input 2?

5 10 3
0 1 4 6 7

Sample Output 2

0

Sample Input 3

12 1000000000 5
18501490 45193578 51176297 126259763 132941437 180230259 401450156 585843095 614520250 622477699 657221699 896711402

Sample Output 3

199999992

本题不难,复杂度为O(n)

#include <stdio.h>
long long a[100005], n, l, w, ans;
int main()
{
	scanf("%lld %lld %lld", &n, &l, &w);
	for (int i = 0; i < n; i++)
	{
		scanf("%lld", &a[i]);
		if (i == 0)
		{
			if (a[i] > 0)
				if (a[i] < w)
					ans++;
				else
				{
					ans += a[i] / w;
					if (a[i] % w != 0)
						ans++;
				}
		}
		else
		{
			if (i == n - 1 && a[i] + w < l)
			{
				if (l - 2 * w < a[i])
					ans++;
				else
				{
					ans += (l - a[i] - w) / w;
					if ((l - a[i] - w) % w != 0)
						ans++;
				}
			}
			if (a[i] - a[i - 1] > w)
			{
				ans += (a[i] - a[i - 1] - w) / w;
				if ((a[i] - a[i - 1]) % w != 0)
					ans++;
			}
		}
	}
	printf("%lld", ans);
	return 0;
}