54 条题解
-
3
jiangang LV 8 @ 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; } -
0
#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;
} -
0
feidaoluoye LV 9 @ 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;
} -
0
二分+递推
发现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;
}
``` -
0
方晨羽——福利站（pascal）
评测状态 Accepted
题目 P1339 羽毛
递交时间 2016-08-31 14:23:24
代码语言 Pascal
评测机 ShadowShore
消耗时间 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.
-
0
liyinghaowei LV 10 @ 2014-10-04 16:14:44
var
a:array[1..100000]of longint;
i,n,ans,sum:longint;
//sum:int64;
begin
readln(n);
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. -
0
ffffffff12138 LV 7 @ 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
readln (n);
for i:=1 to n do
begin
readln (ipt[i]);
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. -
0
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
readln (n);
for i:=1 to n do
begin
readln (ipt[i]);
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. -
0
var
a:array[1..20000] of longint;
n,count1,count2,i,max:longint;
begin
readln(n);
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. -
0
var
a:array[1..20000] of longint;
n,count1,count2,i,max:longint;
begin
readln(n);
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. -
0
#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;
} -
0
dfx3393521 LV 10 @ 2009-10-26 17:47:22
3
5 5 5
路过用那个公式就过不了3
1 1 1 也不行 -
0
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; -
0
编译通过...
├ 测试数据 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
readln(n);
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. -
0
Melody1992 LV 10 @ 2009-08-18 20:17:46
好吧我理解了。。ORZ
jiangang
LV 8
@ 2017-08-10 10:54:44
