2013
11-10

# Best Cow Fences

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.

* 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.

* 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.

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


6500


//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;

public class Main {

static int n,k;
static final int N = 100000+100,que[] = new int[N];
static double DP[] = new double[N] , sum[] = new double[N];

public static int Get_Num(StreamTokenizer cin) throws Exception{
cin.nextToken();
return (int)cin.nval;
}

public static void main(String []args) throws Exception{

int i,j;
double temp;

//n = cin.nextInt();
//k = cin.nextInt();
n = Get_Num(in);
k = Get_Num(in);
sum[0] = 0.0;
for(i=1;i<=n;++i){
temp = (double) Get_Num(in);
temp*=1000.0;
sum[i] = sum[i-1]+temp;
}
i = (int) solve();
System.out.println(i);
}

public static boolean G(int a,int b,int c){
if((sum[c]-sum[a])*(b-a)<=(sum[b]-sum[a])*(c-a))
return true;
return false;
}

public static int solve(){

double Max;
int left=0,right=0,i,j;
for(i=k;i<=n;++i){
while(right-left>=2 && G(que[right-2],que[right-1],i-k))
--right;
que[right++] = i-k;

DP[i] = (sum[i] - sum[que[left]])/(i-que[left]);
while(left< right-1 && (DP[i]<=((sum[i]-sum[que[left+1]])/(i-que[left+1])))){
left++;
DP[i] = (sum[i] - sum[que[left]])/(i-que[left]);
}
}
for(Max=0.0,i=1;i<=n;++i)
Max = Max>DP[i]?Max:DP[i];
return (int)Max;
}
}

1. [email protected]

2. 一开始就规定不相邻节点颜色相同，可能得不到最优解。我想个类似的算法，也不确定是否总能得到最优解：先着一个点，随机挑一个相邻点，着第二色，继续随机选一个点，但必须至少有一个边和已着点相邻，着上不同色，当然尽量不增加新色，直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

3. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1

4. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

5. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}