USACO 2017 February Contest, Silver Problem 2. Why Did the Cow Cross the Road II

原题下载

USACO2017-FEB-S2

答案:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> A;

int main() {
int N, K, B;
cin >> N >> K >> B;

A.resize(B);
for (int i = 0; i < B; i++) {
cin >> A[i];
}
sort(A.begin(), A.end());

int hia = 0;
while (hia < B && A[hia] <= K) {
hia++;
}

int result = hia;
for (int i = 0; i < B; i++) {
if (A[i] + K > N) {
break;
}
while (hia < B && A[hia] <= A[i] + K) {
hia++;
}
result = min(result, hia – i – 1);
}
cout << result << endl;

return 0;
}