POJ2018总结

Best Cow Fences

题目来源

Description

Farmer John’s farm consists of a long row of N (1 <= N <= 100,000)fields. Each field contains a certain number of cows, 1 <= ncows <= 2000.

FJ wants to build a fence around a contiguous group of these fields in order to maximize the average number of cows per field within that block. The block must contain at least F (1 <= F <= N) fields, where F given as input.

Calculate the fence placement that maximizes the average, given the constraint.

Input

* Line 1: Two space-separated integers, N and F.

* Lines 2..N+1: Each line contains a single integer, the number of cows in a field. Line 2 gives the number of cows in field 1,line 3 gives the number in field 2, and so on.

Output

* Line 1: A single integer that is 1000 times the maximal average.Do not perform rounding, just print the integer that is 1000*ncows/nfields.

Sample Input

10 6
6 
4
2
10
3
8
5
9
4
1

Sample Output

6500

我的代码

求子段的最大平均值，其中子段有最小长度要求。设dp[i]为以i为结尾的子段的最大平均值，且子段的最小长度为f，那么dp[i+1]的取值为，构成dp[i]的子段加上第i+1个数的平均值，与第i+1个数与其前面的f-1个数的平均值。

#include<stdio.h>


int n,f,sum,num;
int fields[100010];
double temp;

int main()
{
	double temp1,temp2,ans;
	scanf("%d%d",&n,&f);
	for (int i=0;i<n;i++)
	{
		scanf("%d",&fields[i]);
	}
	sum=0;num=0;
	for (int i=0;i<f;i++)
	{
		num++;
		sum+=fields[i];
	}
	temp=sum;
	ans=1.0*sum/num;
	for (int i=f;i<n;i++)
	{
		temp1=1.0*(sum+fields[i])/(num+1);
		temp+=fields[i];
		temp-=fields[i-f];
		temp2=1.0*temp/f;
		
		if (temp1>temp2){
			sum+=fields[i];
			num++;
			if (temp1>ans) ans=temp1;
		}else{
			sum=temp;
			num=f;
			if (temp2>ans) ans=temp2;
		}
	}
	printf("%d\n",(int)(ans*1000));
	return 0;
}

反思

Do not perform rounding, just print the integer that is 1000*ncows/nfields.

如果用%.0f输出就是四舍五入，直接转型成int就是舍去尾部。