PAT Advanced 1117 Eddington Number

PAT Advanced 1117 Eddington Number tests binary search (sort first) for the position of t (t < N) and test to see if t meets Eddington Number definition by O(NLogN)

PAT Advenced 1117 Eddington Number

British astronomer Eddington liked to ride a bike. It is said that in order to show off his skill, he has even defined an “Eddington number”, E – that is, the maximum integer E such that it is for E days that one rides more than E miles. Eddington’s own E was 87.

Now given everyday’s distances that one rides for N days, you are supposed to find the corresponding E (<=N).

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N(<=10^5), the days of continuous riding. Then N non-negative integers are given in the next line, being the riding distances of everyday.

Output Specification:

For each case, print in a line the Eddington number for these N days.

Sample Input:

10
6 7 6 9 3 10 8 2 7 8

Sample Output:

6

PAT Advenced 1117 Eddington Number

By definition, Eddington Number is the maximum integer E such that it is for E days that one rides more than E miles, so we can find this number in O(NLogN) time by following steps:

  1. Sort the input
  2. Get the minimum number between the size of the input N and the maximum miles, we can think about this, Eddiongton Number will never be larger than these two
  3. retry all the numbers from 0 to the mimium testing value from step 2, use binary search to find the right position in the sorted input of this testing value let’s call it e, now we can know for how many days that have larger miles than e, and if the number of days is larger than or equal to e, then e is Eddington Number by definition
  4. We test e in decreasing order, so the first e is the maximum Eddington Number, since N < 10^5, we now it could be solved in O(NLogN), this should solve the probelm without TLE.

The following is the C++ source code that could be accepted by PAT OJ to pass this PAT Advenced 1117 Eddington Number:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <vector>
#include <cstdio>
#include <algorithm>

using std::vector;

int bs(const vector<int> &nums, int l, int r, int t) {
	if (l >= r) {
		return l;
	}

	int mid = l + (r - l) / 2;
	if (nums[mid] <= t) {
		return bs(nums, mid + 1, r, t);
	} else {
		return bs(nums, l, mid, t);
	}
	return -1;
}

int main() {

	int n;
	vector<int> nums;

	scanf("%d", &n);
	nums.resize(n);

	for (int i = 0; i < n; ++i) {
		scanf("%d", &nums[i]);
	}

	std::sort(nums.begin(), nums.end());

	int start = std::min(n, nums[nums.size() - 1]);
	int len = nums.size();
	for (int i = start; i >= 0; --i) {
		int ret = bs(nums, 0, len, i);
		if (len - ret >= i) {
			printf("%d\n", i);
			return 0;
		}
	}
	return -1;
}

Note that the Binary Search is very tricky to be implemented, be careful about the base cases, from the testing result, there is a large data set, so we have to use binary search, otherwise, it will exceeds the time limit, the 3rd test case is the large data set test:

测试点	结果	用时(ms)	内存(kB)	得分/满分
0	答案正确	3	384	13/13
1	答案正确	3	380	3/3
2	答案正确	2	384	3/3
3	答案正确	25	768	4/4
4	答案正确	3	384	1/1
5	答案正确	6	384	1/1

Summary

PAT Advanced 1117 Eddington Number tests binary search (sort first) for the position of t (t < N) and test to see if t meets Eddington Number definition by O(NLogN)

Written on November 29, 2016