企业官网建设流程全解析

题目描述

在教皇约翰保罗二世去世之际，美国周刊杂志《时代》观察到，在100100100年期间选出教皇数量最多的是282828位，时间从867867867年（阿德里安二世）到965965965年（约翰十三世）。这是一个非常有趣的冷知识，但更好的做法是编写一个程序，对于任意长度的时期计算这个数字，而不必是100100100年。此外，天主教会作为一个永恒的机构，就我们所能预测的范围而言，我们希望确保我们的程序在永世中保持有效。

编写一个程序，给定每位教皇当选的年份列表和一个正整数YYY，计算在YYY年期间内任职的教皇的最大数量，以及该时期中第一位和最后一位教皇的当选年份。注意，给定年份NNN，从年份NNN开始的YYY年期间是从年份NNN的第一天到年份N+Y−1N + Y - 1N+Y−1的最后一天的时间间隔。如果出现并列，即如果有多个YYY年期间具有相同的最大教皇数量，程序应只报告最古老的那一个。

输入格式

输入将包含多个测试用例，每个测试用例如下所述。连续的测试用例之间由一个空行分隔。

输入的第一行包含一个正整数YYY，即我们感兴趣的期间的年数。第二行包含另一个正整数，即教皇数量PPP。其余PPP行中的每一行包含一位教皇的当选年份，按时间顺序排列。已知P≤100000P \le 100000P≤100000，并且文件中的最后一年LLL满足L≤1000000L \le 1000000L≤1000000，且Y≤LY \le LY≤L。

输出格式

对于每个测试用例，输出包含一行，其中有三个由空格分隔的整数：YYY年期间内教皇的最大数量、该时期中第一位教皇的当选年份以及该时期中最后一位教皇的当选年份。

样例输入

5 20 1 2 3 6 8 12 13 13 15 16 17 18 19 20 20 21 25 26 30 31

样例输出

6 16 20

题目分析

本题要求在给定的教皇当选年份序列中，找到一个长度为YYY年的窗口，使得窗口内包含的年份数量最多。窗口定义为从年份NNN的第一天到年份N+Y−1N + Y - 1N+Y−1的最后一天，因此一个年份yearyearyear落在以NNN为起始的窗口内当且仅当N≤year≤N+Y−1N \le year \le N + Y - 1N≤year≤N+Y−1。等价地，对于窗口内任意两个年份aaa和bbb（a≤ba \le ba≤b），它们属于同一个YYY年窗口的条件是b−a<Yb - a < Yb−a<Y。

题目要求找到包含年份数量最多的窗口，并输出该窗口内的第一个年份和最后一个年份。如果存在多个窗口具有相同的最大数量，则选择最古老的那个，即第一个年份最小的那个。由于输入年份按时间顺序排列，我们只需要在扫描过程中维护当前窗口，并在窗口大小超过历史最大值时更新答案。当窗口大小等于历史最大值时，由于我们按时间顺序扫描，当前窗口的起始年份不会小于历史最大窗口的起始年份，因此不需要更新，这样自然满足“最古老”的要求。

解题思路

使用双端队列（deque\texttt{deque}deque）维护当前窗口内的年份。按顺序读入每个教皇的当选年份，对于每个新年份yearyearyear，尝试将其加入窗口。如果加入后窗口内最旧的年份frontfrontfront与yearyearyear的差值小于YYY，则说明yearyearyear可以加入当前窗口，直接将其加入队列尾部。否则，当前窗口无法容纳yearyearyear，需要先将队列中所有与yearyearyear的差值大于等于YYY的年份从队首移除，直到队首年份与yearyearyear的差值小于YYY，然后将yearyearyear加入队列尾部。

在移除元素之前，需要检查当前窗口的大小是否超过了历史最大数量。如果超过了，则更新最大数量、最大窗口的起始年份（队首）和结束年份（队尾）。由于我们按时间顺序处理，当窗口大小等于历史最大值时，不更新答案，从而保证选择的是最古老的窗口。

处理完所有年份后，还需要再检查一次最终窗口的大小是否超过历史最大值，因为最后一个窗口可能没有被检查。

时间复杂度为O(P)O(P)O(P)，因为每个年份最多入队一次、出队一次。空间复杂度为O(P)O(P)O(P)，用于存储队列中的年份。

代码实现

// Popes// UVa ID: 957// Verdict: Accepted// Submission Date: 2017-03-06// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intperiod,popes,year;intmaxCount,maxStart,maxEnd;while(cin>>period){cin>>popes>>year;deque<int>years;years.push_back(year);maxCount=1,maxStart=year,maxEnd=year;for(inti=2;i<=popes;i++){cin>>year;if(year-years.front()<period)years.push_back(year);else{if(years.size()>maxCount){maxCount=years.size();maxStart=years.front();maxEnd=years.back();}while(!years.empty()){if(year-years.front()<period){years.push_back(year);break;}years.pop_front();}}}if(years.size()>maxCount){maxCount=years.size();maxStart=years.front();maxEnd=years.back();}cout<<maxCount<<' '<<maxStart<<' '<<maxEnd<<'\n';}return0;}

总结

本题的核心是滑动窗口技术，利用双端队列维护一个年份跨度小于YYY的窗口。由于年份按时间顺序给出，窗口的起始和结束年份自然对应队列的首尾元素。在窗口滑动过程中，及时更新最大窗口的信息，并利用扫描顺序保证在并列时选择最古老的窗口。需要注意边界情况，例如只有一个教皇或最后一个窗口未被检查的情况。该算法时间复杂度为O(P)O(P)O(P)，空间复杂度为O(P)O(P)O(P)，能够高效处理P≤100000P \le 100000P≤100000的数据规模。