LA3177长城守卫

题意：

有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长城守卫

最新文章

热门文章