poj2018 Best Cow Fences

Time Limit: 1000MS

Memory Limit: 30000K
Total Submissions: 9985

Accepted: 3237
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

Sample Output
6500
이 문제는 사율 최적화로 할 수도 있고 2점으로 할 수도 있는데 나는 2점 방법을 썼다.
제목: n개의 소의 자신의 가치를 주고 연속적이고 수량이 F와 같은 구간을 찾아내 이 구간 내의 소의 평균 가치를 가장 크게 한다.
사고방식: 이분 매거로 평균치ave를 들면 모든 소의 가치가ave를 빼고 f 길이를 초과한 구간이 연속적으로 이 구간의 가치가 0보다 큰지 확인한다. 만약에 찾을 수 있다면 이 평균치가 도달할 수 있다는 것을 의미한다.먼저 각 a[i]에서ave를 빼면 b[i]를 얻고 dp[i]로 i를 끝으로 하는 구간의 연속 길이가 f의 최대 연속 구간보다 크다는 것을 나타낸다. maxx[i]는 i를 끝으로 하는 최대 연속 구간과,sum[i]는 1~i의 가치를 합치면 maxx[i]=max(maxx[i-1]+b[i], b[i]), dp[i]=max[i-f+1]+sum[i]-sum[i-f+1]를 표시하고 i-f+1]가 있는지 판단한다.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define inf 99999999
#define maxn 100050
#define eps 1e-6
double sum[maxn],a[maxn],b[maxn],dp[maxn],maxx[maxn];
int main()
{
    int n,m,i,j,f,ant;
    double l,r,mid,ans;
    while(scanf("%d%d",&n,&f)!=EOF)
    {
        l=2000.0;r=1.0;
        for(i=1;i<=n;i++){
            scanf("%lf",&a[i]);
            l=min(l,a[i]);
            r=max(r,a[i]);//     ，       
        }
        while(r-l>eps){
            mid=(l+r)/2.0;
            sum[0]=0;maxx[0]=0;
            for(i=1;i<=n;i++){
                b[i]=a[i]-mid;
                sum[i]=sum[i-1]+b[i];
                maxx[i]=max(b[i],maxx[i-1]+b[i]);
            }
            ans=sum[f];
            for(i=f+1;i<=n;i++){
                dp[i]=maxx[i-f+1]+sum[i]-sum[i-f+1];
                if(ans=0)l=mid;
            else r=mid;
        }
        ant=1000*r;
        printf("%d
",ant);
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

|NOIOJ|2분|04: 네트워크 관리자

심판위원회는 인터넷 라인을 구매하기 위해 현지의 한 인터넷 솔루션 제공 업체에 연락하여 일정한 수량의 등장망 라인을 제공할 수 있도록 요구했다.심판위원회는 네트워크가 길어질수록 좋아져 선수들 사이의 거리가 가능한 한...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

poj2018 Best Cow Fences

좋은 웹페이지 즐겨찾기