UVa957 - Popes (Binary Search)

題目大意：

我們有過去歷史教皇選舉的資料，現在我們需要知道在 x 年期間中的教皇選舉最多次，並告訴我們期間開始選舉的教皇與期間最後選舉教皇

我們會給定已經排序好的選舉日期，就請寫出程式找出答案吧！

分析：

這題可以用兩種方式去解，一種是最長區間覆蓋長，屬於動態規劃，另一種是 Binary Search，這裡我們使用 Binary Search 去 AC 此題。

如果還不太懂 LIS 是甚麼問題，建議看看 演算法知識 - Binary Search 二分搜尋，這裡有對於此演算法有完整的介紹

焦點回到題目上，解開題目的小設計

這題總共需要求出 3 個答案，第一是期間內的最多選舉次數，再來是期間內的第一次選舉與最後一次選舉。

我們透過題目的公式 \( N+Y-1 \)，其中 N 等於 \(一開始可查詢選舉年份 + Y 期間 - 1 = 符合題目條件的最終可查詢選舉年份 \)，我們只需要對每一個選舉年份 + Y - 1，就可以找出每個期間的選舉次數，並記錄最大的選舉次數與一開始可選舉日期以及 Binary Search 找到的最後大於等於最終可查詢的選舉年份即可。

last = bs(i,p,num[i]+y-1) ; //bs binary Search，以下簡稱 bs
// num[i]+y-1 表示最終可查詢年份 , last = 透過 bs 找出在此數列中的大於等於最終可查詢年份之選舉年份位置
first = i ; // first = 一開始可查詢選舉年份在此數列中的位置
large = last - first +1 ; // large = 最終可查詢年份 - 最初可查詢年份 + 1，表示裡面有多少選舉

透過迴圈針對每一次的選舉進行查詢，並記錄最大即可。

心得

老話一句，英文很重要QQ，我到底因為英文不好吃了幾次虧啦…。

我看了很久QQ，查了好多英文單字，我竟然連 Popes 都不知道是甚麼QQ，我還需要好好磨練、好好讓自己的英文能力進步啦，英文真的好重要好重要，可是我每次只要回到家都沒有再讀英文…，我也太沒用了八。

好啦，題外話講多了，其實我在寫這一題時，我發現這題其實沒有很難寫，但是卡在解決二分搜尋的一些小毛病，例如要大於等於…之類的，最近在增強自己沒有透過紙筆也能夠進行表達以及程式思考的方式，加強我自己對於一些簡單判斷的基礎能力，如果可以將簡單判斷減少依賴，或許我在表達時就可以表達的流暢些，我常常在口述表達自己時長不完善，但只要透過文字我就可以很能夠表達我自己，因為文字我可以做 Review，但口述卻沒辦法。

之後也要好好努力，成為一位不愧對過去自己的人。

題目程式碼

其實就是沒有附上說明的程式碼，看得懂跟說得出來真的是兩回事，也許還有人覺得我說的很差，不過我已經盡力解釋。希望可以幫助到各位。

也希望大家想要學習的知識都可以快速學習而成，不要因為自身的環境不足而學習不到。

於是這裡就補述一些題目給的資料範圍限制與標頭檔了。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAX 1000010
using namespace std;
int y , p , temp , num[MAX] ;
int max_large , max_first , max_last ;

int bs(int l , int r , int v){
    int m ;
    while(l < r){
        //debug
        //cout << num[l] << ' ' << num[r] << '\n' ;
        m = (l+r) / 2 ;
        if(num[m] <= v) l = ++m;
        else r = m;
    }
    return m-1 ;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    //freopen("out.txt" , "w" , stdout);
#endif // LOCAL
    int large , first , last ;
    while(cin >> y){
        max_large = max_first = max_last = 0 ;
        large = first = last = 0 ;
        cin >> p ;
        for(int i = 0 ; i < p ; i++) cin >> num[i] ;
        for(int i = 0 ; i < p ; i++){
            last = bs(i,p,num[i]+y-1) ;
            first = i ;
            large = last - first +1 ;
            //debug
            //cout << "i = " << i << " binary search range " << num[first] << "-" << num[last] << " result is " << large << '\n' ;
            if(large >  max_large){
                max_large = large ;
                max_first = first ;
                max_last = last ;
            }
        }
        cout << max_large << " " << num[max_first] << " " << num[max_last] << '\n' ;
    }

    return 0;
}