題意：
? ? ?有n個人圍成一個圈，每個人都有r[i]個禮物，任意兩個相鄰的人的禮物不能有重復的，問滿足所有相鄰不重復的最少禮物種數是多少？就是問最少多少種禮物能讓任意相鄰的兩個人的禮物不重復。


思路：
? ? ?比較有意思的一個題目，首先這個題目很多人包括我的第一反應就是任意兩個相鄰的和中最大的那個和，但是這樣只適應偶數的情況，那么我們就分兩種情況來考慮，首先是偶數，偶數比較簡單，就是任意兩個相鄰的數都做一個和，別忘記1，n也做一次和，也就是這樣Ans = max(Ans ,num[i] + num[i-1])最后直接輸出Ans就行了，為什么這樣是正確的？我們可以這樣理解，我們可以讓奇數的位置盡可能的小，偶數的位置盡可能的大（可以調換），那么最后的n是盡可能的大的，而1是盡可能的小的，隨意不沖突，這樣的話最終的答案就是某一對的最大值了，下面考慮奇數的情況，奇數的情況不能直接像偶數那樣枚舉，因為最后的n是盡可能的小，而1也是盡可能的小，顯然不是最優，我們可以先把1固定，就是1,2,3,4..r[1]，而偶數的位置盡可能的小，奇數的位置盡可能的大，這樣n是盡可能大的，而1被固定了，是盡可能小的，這樣就不沖突了，但是這種情況的答案是不能直接算出來的，我們可以二分去枚舉答案，對于每一個當前值mid,我們就把mid想象成最大的個數，然后去判斷是否滿足要求，判斷的過程是開兩個數組，lift[i],right[i],前面的是表示當前這一位用了多少個r[1]以下的數字，第二個數組表示的是當前這一位用了多少個r[1]以上的數字，對于每一位我們根據奇偶來判斷是優先在lift上加還是優先在right上加，對于某一位，當上一位剩下的lift+剩下的right < r[i]的時候，就表示沖突了，如果過程中沒有沖突，最后的時候我們還要判斷n,1是否沖突，因為lift[1] = 下邊界的，所以lift[n]必須等于0才行，這也是為什么lift和right的邊界是r[1]的原因，如果是別的數字的話最后就沒有辦法判斷n,1是否沖突了。






#include<stdio.h>


int num[110000];
int lift[110000] ,right[110000];


bool ok(int mid ,int n)
{
? ? lift[1] = num[1];
? ? right[1] = 0;
? ? int ll = num[1] ,rr = mid - num[1];
? ? for(int i = 2 ;i <= n ;i ++)
? ? {
? ? ? ?if(i % 2 == 0)
? ? ? ?{
? ? ? ? ? ?if(ll - lift[i-1] >= num[i])
? ? ? ? ? ?{
? ? ? ? ? ? ? ?lift[i] = num[i];
? ? ? ? ? ? ? ?right[i] = 0;
? ? ? ? ? ?}
? ? ? ? ? ?else if(ll - lift[i-1] + rr - right[i-1] >= num[i])
? ? ? ? ? ?{
? ? ? ? ? ? ? ?lift[i] = ll - lift[i-1];
? ? ? ? ? ? ? ?right[i] = num[i] - lift[i];
? ? ? ? ? ?}
? ? ? ? ? ?else return 0;
? ? ? ?}
? ? ? ?else
? ? ? ?{
? ? ? ? ? ?if(rr - right[i-1] >= num[i])
? ? ? ? ? ?{
? ? ? ? ? ? ? ?right[i] = num[i];
? ? ? ? ? ? ? ?lift[i] = 0;
? ? ? ? ? ?}
? ? ? ? ? ?else if(rr - right[i-1] + ll - lift[i-1] >= num[i])
? ? ? ? ? ?{
? ? ? ? ? ? ? ? right[i] = rr - right[i-1];
? ? ? ? ? ? ? ? lift[i] = num[i] - right[i];
? ? ? ? ? ?}
? ? ? ? ? ?else return 0;
? ? ? ?}
? ? }
? ? return !lift[n];
}


int main ()
{
? ? int n ,i ,Max ,Min;
? ? while(~scanf("%d" ,&n) && n)
? ? {
? ? ? ?Max = -1 ,Min = 110000;
? ? ? ?for(i = 1 ;i <= n ;i ++)
? ? ? ?{
? ? ? ? ? scanf("%d" ,&num[i]);
? ? ? ? ? if(Max < num[i]) Max = num[i];
? ? ? ? ? if(Min > num[i]) Min = num[i];
? ? ? ?}
? ? ? ?if(n == 1)
? ? ? ?{
? ? ? ? ? ? printf("%d\n" ,num[1]);
? ? ? ? ? ? continue;
? ? ? ?}
? ? ? ?if(!(n%2))
? ? ? ?{
? ? ? ? ? num[0] = num[n];
? ? ? ? ? int Ans = 0;
? ? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? ? if(Ans < num[i] + num[i-1])
? ? ? ? ? Ans = num[i] + num[i-1];
? ? ? ? ? printf("%d\n" ,Ans);
? ? ? ? ? continue;
? ? ? ?}
? ? ? ?int low ,up ,mid ,Ans;
? ? ? ?low = Min ,up = Max * 3;
? ? ? ?while(low <= up)
? ? ? ?{
? ? ? ? ? mid = (low + up) >> 1;
? ? ? ? ? if(ok(mid ,n)) Ans = mid ,up = mid - 1;
? ? ? ? ? else low = mid + 1;
? ? ? ?}
? ? ? ?printf("%d\n" ,Ans);
? ? }
? ? return 0;
}
? ? ? ?
? ? ? ?
? ? ? ? ??

總結

以上是生活随笔為你收集整理的LA3177长城守卫的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。