[UVA] 957 - Popes
Popes
| Popes |
On the occasion of Pope John Paul II death, the American weekly magazine Time observed the largest number of Popes to be selected in a 100-year period was 28, from 867 (Adrian II) to 965 (John XIII). This is a very interesting piece of trivia, but it would be much better to have a program to compute that number for a period of any length, not necessarily 100 years. Furthermore, the Catholic Church being an eternal institution, as far as we can predict it, we want to make sure that our program will remain valid per omnia secula seculorum.
Write a program that given the list of years in which each Pope was elected and a positive number Y, computes the largest number of Popes that were in office in a Y-year period, and the year of election for the first and last Popes in that period. Note that, given a year N, the Y-year period that starts in year N is the time interval from the first day of year N to the last day of year N + Y - 1. In case of a tie, i.e., if there is more that one Y-year period with the same largest number of Popes, your program should report only the most ancient one.
Input
The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line.
The first line of the input contains a positive integer Y, the
number of years of the period we are interested in. The second line contains
another positive integer, the number of Popes, P. Each of the remaining P lines
contains the year of election of a Pope, in chronological order. We know that
P
100000 and also that the last year L in the file is such
L1000000, and
that YL.
Output
For each test case, write to the output contains a single line with three integers, separated by spaces: the largest number of Popes in a Y-year period, the year of election of the first Pope in that period and the year of election of the last Pope in the period.
Sample Input
5 20 1 2 3 6 8 12 13 13 15 16 17 18 19 20 20 21 25 26 30 31
Sample Output
6 16 20
MIUP'2006
題目描述：
每個教宗都有任期的時間，現在給你按照時間的任期時間，問連續 Y 年內，最多有幾個教宗任期，
並且輸出起頭與結束的任期時間。
題目解法：
就是求最長區間，且這個區間總和小於等於 Y。
是個 O(n) 作法。
#include <stdio.h>
int main() {
int Y, P, L[100000];
int i;
while(scanf("%d", &Y) == 1) {
scanf("%d", &P);
for(i = 0; i < P; i++)
scanf("%d", &L[i]);
int r = 0;
int mx = -1, al, ar;
for(i = 0; i < P; i++) {
while(r < P && L[r] <= L[i]+Y-1)
r++;
if(r-i > mx) {
mx = r-i;
al = L[i], ar = L[r-1];
}
}
printf("%d %d %d\n", mx, al, ar);
}
return 0;
}