首页 > 专题系列 > Java解POJ > POJ 2018 Best Cow Fences [解题报告] Java
2013
11-10

POJ 2018 Best Cow Fences [解题报告] Java

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;

   StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		
	//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;
    }