2058: Find the Section
| Result | TIME Limit | MEMORY Limit | Run Times | AC Times | JUDGE |
|---|---|---|---|---|---|
 |
3s | 8192K | 569 | 128 | Standard |
Input
The first line of each test case is an integer N (<=100000). And the following lines have N floating point numbers. The last case have the N equal to zero, which you should not process.
Output
For each test case print "Case #T:" in the first line, where the T starts from 1. And the second line the sentence "The section from N1(th) to N2(th) have the max sum S", which means the numbers in the table from N1(th) to N2(th) have the sum S and S is the maximum you can find. N1, N2 are integers, and S is rounded to the nearest 0.001.
Note: If two sections have the same max sum, find the longer one and the one appears first. The length of the section can be zero which have a sum of zero, and it is from 0(th) to 0(th).
Sample Input
5 1 3.1 -2 7.35 -4 10 -5 -4 -3 -2 -1 0 1 2 3 4 0
Sample Output
Case #1: The section from 1(th) to 4(th) have the max sum 9.450 Case #2: The section from 6(th) to 10(th) have the max sum 10.000
Problem Source: coldcpp
#include<stdio.h>
int main()
{
int n;
int i,j;
int l=1;
while(scanf("%d",&n)==1&&n)
{
double a,s=1<<31,max=1<<31;
int ti=1,tj=1,temp=1;
for(i=1;i<=n;i++)
{
scanf("%lf",&a);
if(s>=0) s+=a;//包含0 用'='
else s=a,temp=i;
if(s>max) max=s,ti=temp,tj=i;
else if(s==max&&(i-temp>tj-ti)) ti=temp,tj=i;
}
if(max<0) max=ti=tj=0;
printf("Case #%d:/n",l++);
printf("The section from %d(th) to %d(th) have the max sum %.3lf/n",ti,tj,max);
}
return 0;
}