/ Vijos / 题库 / 羽毛 /

# 54 条题解

• @ 2017-08-10 10:54:44

/*
数学方法，百度。
因为相邻的不能有重复颜色，所以颜色种数至少是相邻两个的羽毛数总和
又考虑一共有m根羽毛，相同颜色的羽毛最多有(N div 2)根，因此颜色至少有m div (N div 2)种｛注意是上取整｝。
完。
*/

``````#include<stdio.h>
#include<math.h>
int ans;
int a[20001],
m,
n,
i,
j;
int main()
{
scanf("%d",&n);
for (i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=1;i<n;++i)
if (a[i]+a[i+1]>ans) ans=a[i]+a[i+1];
//羽毛数
for (i=1;i<=n;++i) m+=a[i];

double mm=m,nn=n,tem;
//羽毛数/每个颜色的最多羽毛数
tem=ceil(mm/((int)(nn/2)));
if ((int)tem>ans) ans=(int)tem;
printf("%d",ans);
return 0;
}
``````
• @ 2016-12-24 23:18:41

#include<cstdio>
const int N=20005;
long long a[N],max=0,sum=0;
int main()
{int n,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
a[n+1]=a[1];
for(i=1;i<=n;i++)
{sum+=a[i];
max=max>a[i]+a[i+1]?max:a[i]+a[i+1];
}
sum=(sum+(n/2)-1)/(n/2);
max=max>sum?max:sum;
printf("%lld",max);
return 0;
}

• @ 2016-12-14 20:46:36

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxa 20100
using namespace std;
int a[maxa],l[maxa],r[maxa],n;
bool comp(int p)
{
int x= a[1],y= p-a[1],i;
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
l[1] =x;
r[1] = 0;
for(i=2;i<=n;++i)
{
if(i%2==0)
{
l[i] = min(x-l[i-1],a[i]);
r[i] =a[i]-l[i];
}
else
{
r[i] = min(y-r[i-1],a[i]);
l[i] = a[i]-r[i];
}
}
return l[n]==0;
}
int main()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%d",&(a[i]));
int L=0,R=0;
for(i=1;i<n;++i)
{
L = max(L,a[i]+a[i+1]);
R = max(R,3*a[i]);
}
R =max(R,3*a[n]);
L = max(L,a[1]+a[n]);
if(n%2==1){
while(L<=R)
{
int mid =(L+R)/2;
if(comp(mid)==true)
{
R =mid-1;
}
else
L = mid+1;
}
}
printf("%d",L);
return 0;
}

• @ 2016-11-16 15:37:00

二分+递推
发现c++代码太少，发一个
```
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 20010
using namespace std;
int n,a[maxn],c[maxn],b[maxn];//b与a[1]最小或大相同数，c与a[1]最大或小不同数
int l=0,r;
bool check(int x){
int i;
memset(c,0,sizeof(c));
memset(b,0,sizeof(b));
int temp=a[1];b[1]=a[1];
for(i=2;i<=n;i++){
if(i!=n){
if(i%2!=0){
if(a[i]<x-c[i-1]-temp){
c[i]=a[i];continue;
}
else c[i]=max(x-c[i-1]-temp,0);
b[i]=a[i]-c[i];
}
if(i%2==0){
if(a[i]<temp-b[i-1]){
b[i]=a[i]; continue;
}
else b[i]=max(temp-b[i-1],0);
c[i]=a[i]-b[i];
}
}
else{
if((a[i]+a[1]+a[i-1]-b[i-1])<=x) return true;
else return false;
}
}
}
int main(){
freopen("F.in","r",stdin);
freopen("F.out","w",stdout);
int i;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
}
a[0]=a[n]; a[n+1]=a[1];
int tmp=0;
if(n==1){
printf("%d",a[1]);
return 0;
}
for(i=0;i<=n;i++){
tmp=max(tmp,a[i]);
l=max(l,a[i]+a[i+1]);
}
r=tmp*3;
if(n%2==0) {
printf("%d",l);
return 0;
}

while(l<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d",l);
return 0;
}
```

• @ 2016-08-31 14:26:53

方晨羽——福利站（pascal）
评测状态 Accepted
题目 P1339 羽毛
递交时间 2016-08-31 14:23:24
代码语言 Pascal
消耗时间 30 ms
消耗内存 892 KiB
评测时间 2016-08-31 14:23:25
```pascal var a:array[0..20000]of longint; i,n,ans,sum:longint; begin readln(n); sum:=0; for i:=1 to n do begin readln(a[i]); inc(sum,a[i]); end; ans:=a[1]+a[n]; for i:=1 to n-1 do if a[i]+a[i+1]>ans then ans:=a[i]+a[i+1]; if round(sum/(n div 2))+1 >ans then ans:=round(sum/(n div 2))+1; writeln(ans); readln; end. ```

• @ 2014-10-04 16:14:44

var
a:array[1..100000]of longint;
i,n,ans,sum:longint;
//sum:int64;
begin
for i:=1 to n do begin readln(a[i]);inc(sum,a[i]);end;
ans:=a[1]+a[n];
for i:=1 to n-1 do if a[i]+a[i+1]>ans then ans:=a[i]+a[i+1];
if round(sum/(n div 2))+1 >ans then ans:=round(sum/(n div 2))+1;
writeln(ans);
end.

• @ 2014-05-04 18:25:27

program life;
var
n,i,j,max,sum:longint;
ipt:array[1..20000] of longint;
function maxer(x,y:longint):longint;
begin
if x>y then maxer:=x
else maxer:=y;
end;
begin
for i:=1 to n do
begin
inc (sum,ipt[i]);
end;
max:=ipt[1]+ipt[n];
for i:=2 to n do
max:=maxer(max,ipt[i]+ipt);

writeln (maxer(max,trunc(sum/(n div 2))+1));
end.

• @ 2014-05-04 18:25:23

program life;
var
n,i,j,max,sum:longint;
ipt:array[1..20000] of longint;
function maxer(x,y:longint):longint;
begin
if x>y then maxer:=x
else maxer:=y;
end;
begin
for i:=1 to n do
begin
inc (sum,ipt[i]);
end;
max:=ipt[1]+ipt[n];
for i:=2 to n do
max:=maxer(max,ipt[i]+ipt);

writeln (maxer(max,trunc(sum/(n div 2))+1));
end.

• @ 2014-05-04 18:24:53

var
a:array[1..20000] of longint;
n,count1,count2,i,max:longint;
begin
max:=0;
for i:=1 to n do begin readln(a[i]);max:=max+a[i];end;
count1:=a[1]+a[n];
for i:=1 to n-1 do
begin
if (a[i]+a)>count1 then count1:=a[i]+a;
end;
count2:=round(max/(n div 2));
if count1>count2 then writeln(count1)
else writeln(count2+1);
end.

• @ 2014-05-04 18:24:42

var
a:array[1..20000] of longint;
n,count1,count2,i,max:longint;
begin
max:=0;
for i:=1 to n do begin readln(a[i]);max:=max+a[i];end;
count1:=a[1]+a[n];
for i:=1 to n-1 do
begin
if (a[i]+a)>count1 then count1:=a[i]+a;
end;
count2:=round(max/(n div 2));
if count1>count2 then writeln(count1)
else writeln(count2+1);
end.

• @ 2013-08-13 00:12:04

#include<iostream>
#include<stdio.h>
using namespace std ;
#define N 20020
int64 a[N];
int n,i;
int ju(
int64 x)
{
__int64 pre=a[0];//表示前一只鹰与第一只鹰羽毛颜色相同的数目
for(i=1;i<n;i++)
{
if(x-a[i-1]<a[i])return 0;
if(i%2)
{
pre=min(a[0]-pre,a[i]);
}
else
{
if(x-a[i-1]-(a[0]-pre)>=a[i])pre=0;
else pre=a[i]-(x-a[i-1]-(a[0]-pre));
}
}
if(n%2)return (pre==0&&a[0]+a[n-1]<=x);
else return (a[0]+a[n-1]<=x);
}
int64 bisearch(int64 low,__int64 high)
{
__int64 mid;
while(low<=high)
{
mid=(low+high)/2;
if(ju(mid))high=mid-1;
else low=mid+1;
}
return low;
}
int main()
{
scanf("%d",&n);
{
__int64 sum=0;
for(i=0;i<n;i++)
{
scanf("%I64d",&a[i]);
sum+=a[i];
}
if(n==1)
{
printf("%I64d\n",a[0]);
}
else printf("%I64d\n",bisearch(0,sum));
}
return 0;
}

• @ 2009-10-26 17:47:22

3

5 5 5

路过用那个公式就过不了

3

1 1 1 也不行

• @ 2009-10-25 15:24:24

Orz 那个公式。

给大家看正统题解吧。^.^

（from 潘帕斯雄鹰)

这个题目是本次比赛的难题，在我找到的众多题审中也没有哪位能轻松AC的。但是一个比较特别的可能是很好找的。那就是相邻的max值作为ans。这种情况在偶数情况下显然是成立的。在我生成数据的时候发现奇数的情况也是大多成立的，反例很好找

3

5

5

5

显然答案是15，而特殊情况的值是10

这样的方法原数据可以拿到60分，但是我对数据进行了改动，在本次比赛中只有30分。

在此声明：本题目并非原创题目，题目来源于浙江省06年省选day2的第四题。

面对这样大的数据范围，一般想到的就是比较特别的算法：数学、贪心、二分查找。

本题就是一道二分查找的题目。

每次判断的规则是：

function check(m : longint) : boolean;

var

l, p, occupy, i : longint;

begin

check := false;

occupy := a[1];

for i := 2 to n do begin

l := m - a[i - 1];

p := a[1] - occupy;

if not odd(i) then

occupy := min(p, a[i])

else

occupy := max(0, a[i] - l + p);

end;

check := occupy = 0;

end;

对于i为偶数的时候尽量用第一个使用的颜色

i为奇数的时候尽量用第二个使用的颜色

如果不够用就增加颜色的种类

因为这样颜色就不可能重复。同时，对于最后访问到的那个数来说，两边都没有用的颜色如果刚好等于那个鹰所需要的颜色，那么必然是一个解

（from 魂牛）

大概说一下我的思路吧：先假设前两个数的和最大（如果不是可以调整）比如这一列数5 7 2 8 35+7=12最大假如现在要判断13是否可行那么令第1个数取第1~5号勋章，第2个数取第6~12号勋章以下从第3个开始判断，基于贪心思想，奇数位上的尽量用1~5以外的，偶数位上尽量用1~5以内的。目的就是为了让第n位上尽可能少与第一个数所用的勋章重复。模拟一下就是：第三个数取5和13（下面1~4，6~12可用）第4个数取1~4和6~9（下面5，10~13可用）第5个数就可以取10~12（尽量不取5）这样就不和第一个数的1~5重复所以13可行

(from 逆铭）

function check(m : longint) : boolean;

var

l, p, occupy, i : longint;

begin

check := false;

occupy := a[1];// [当前鹰的前一只鹰]所占用的[第一只鹰所使用的颜色]数

for i := 2 to n do begin

l := m - a[i - 1];//当前鹰可用的颜色数（即总颜色数减去前一只鹰的颜色数）

p := a[1] - occupy;//当前鹰可以使用的[第一只鹰所使用的颜色]数（即第一只鹰的颜色总数减去前一只鹰使用的[第一只鹰所使用的颜色]数）

if not odd(i) then

occupy := min(p, a[i])//尽可能多地使用第一只鹰所使用的颜色

else

occupy := max(0, a[i] – (l – p) ); //尽可能少地使用第一只鹰所使用的颜色

end;

check := occupy = 0;//最后occupy记录了第n只鹰所使用的[第一只鹰所使用的颜色]数；只有当此值为0时m才为一个可行解

end;

• @ 2009-10-20 10:08:45

我想到了第一个公式却没想到第2个......

数学真的很好很强大！

本沙茶飞过.......

• @ 2009-10-08 08:28:35

神奇公式 很神奇

• @ 2009-09-06 12:16:15

这道题初想有这样一个方法：枚举填i种颜色，然后对于每个颜色，找出最多的颜色还没填完且两两不相邻的鹰填下去。

令c1=相邻和最大值

c2=所有数和/(n div 2) 取上整。

当c1c2时，则会填c1次。所以答案就是max(c1,c2)

• @ 2009-08-29 09:17:41

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

好神奇的公式！！

var

a:array[1..20000] of longint;

n,count1,count2,i,max:longint;

begin

max:=0;

for i:=1 to n do begin readln(a[i]);max:=max+a[i];end;

count1:=a[1]+a[n];

for i:=1 to n-1 do

begin

if (a[i]+a)>count1 then count1:=a[i]+a;

end;

count2:=round(max/(n div 2));

if count1>count2 then writeln(count1)

else writeln(count2+1);

end.

• @ 2009-08-18 20:17:46

好吧我理解了。。ORZ

• @ 2009-06-26 21:17:53

ORZ ChBlossom神牛！

• @ 2009-04-27 20:10:25

那什么神奇的公式似乎有着很大的问题

3

5

5

5

很明显是10

但是他却是16

但却能AC。。。诧异

ID
1339

5

(无)

699

216

31%

4