奶牛专题1：圆圈舞蹈

【问题描述】

     熊大妈的奶牛在时针的带领下，围成了一个圆圈跳舞。由于没有严格的教育，奶牛们之间的间隔不一致。

      奶牛想知道两只最远的奶牛到底隔了多远。奶牛A到B的距离为A顺时针走和逆时针走，到达B的较短路程。告诉你相邻两个奶牛间的距离，请你告诉奶牛两只最远的奶牛

到底隔了多远。

【输入】

     第一行一个整数N，表示有N只奶牛。(2≤N≤100000)

     接下来2～N+1行，第I行有一个数，表示第I-1头奶牛顺时针到第I头奶牛的距离。(1≤距离≤maxlongint，距离和≤maxlongint)

      第N+l行的数表示第N头奶牛顺时针到第1头奶牛的距离。

【输出】

     一行，表示最大距离。

【样例】

Circle.in

5

1

2

3

4

5

Circle.out

7

【样例解析】

      Circle.out所有奶牛I到J之间的距离和到达方式（顺为顺时针，逆为逆时针）如下：

所以，最远的两头奶牛为3到5，距离是7。

话不多说，代码里有足够多的注解，可结合图例一起看。好了，上代码！

#include
#include
#include
#include
using namespace std;
/*1.枚举每一个点 直到找到一个大于圆的一半周长的点2.总长度减去刚找到的长度 进行比较大小（然后选小的） 3.求出每头奶牛与它相离最远奶牛的距离：求两头 1头顺时针最大的1头逆时针最大的
*/ 
int n;
int a[100010];
int c=0;//记录圆的周长 
int ans=0;//记录答案 
void init()
{freopen("circle.in","r",stdin);freopen("circle.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);c+=a[i];}
}void work()
{int sum=0,k=0;//sum记录长度 实现注释1的运算 k记录注释1中找到的那个点(一定要重置为0！)for(int i=1;i<=n;i++){sum+=a[i-1];if(sum>c/2){k=i;break;}} int q=min(sum,abs(c-sum));//记录的是 该点应该选择的路（题上说走顺时逆时中最短的） int q1=min(sum-a[k-1],abs(c-(sum-a[k-1])));//该点记录的是点k的距离（同上）          ans=max(q1,q);//ans=max(ans,q1);//---------------------------------以上几步的实质为二分for(int i=1;i<=n;i++)//从第二头奶牛开始枚举 因为我们可以发现如果奶牛A的最大距离是到D 那么B的最大距离一定是从E开始枚举 {sum-=a[i-1];while(sum<=c/2)   {sum+=a[k+1];k++;}ans=max(ans,min(sum,abs(c-sum)));ans=max(ans,min(sum-a[k-1],abs(c-(sum-a[k-1]))));}printf("%d",ans);
}
int main()
{init();work();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！