首页 > 专题系列 > Java解POJ > POJ 1989 The Cow Lineup [解题报告] Java
2013
11-10

POJ 1989 The Cow Lineup [解题报告] Java

The Cow Lineup

问题描述 :

Farmer John’s N cows (1 <= N <= 100,000) are lined up in a row.Each cow is labeled with a number in the range 1...K (1 <= K <=10,000) identifying her breed. For example, a line of 14 cows might have these breeds:
    1 5 3 2 5 1 3 4 4 2 5 1 2 3

Farmer John’s acute mathematical mind notices all sorts of properties of number sequences like that above. For instance, he notices that the sequence 3 4 1 3 is a subsequence (not necessarily contiguous) of the sequence of breed IDs above. FJ is curious what is the length of the shortest possible sequence he can construct out of numbers in the range 1..K that is NOT a subsequence of the breed IDs of his cows. Help him solve this problem.

输入:

* Line 1: Two integers, N and K

* Lines 2..N+1: Each line contains a single integer that is the breed ID of a cow. Line 2 describes cow 1; line 3 describes cow 2; and so on.

输出:

* Line 1: The length of the shortest sequence that is not a subsequence of the input

样例输入:

14 5
1
5
3
2
5
1
3
4
4
2
5
1
2
3

样例输出:

3

温馨提示:

All the single digit ‘sequences’ appear. Each of the 25 two digit sequences also appears. Of the three digit sequences, the sequence 2, 2, 4 does not appear.

解题代码:

//* @author: ccQ.SuperSupper
import java.util.*;
import java.math.*;
public class Main {
	public static void main(String []args) throws Exception{
		
		int i,j,k,n,ans;
		int way[] = new int[100100];
		int flag[] = new int[10100];
		
		Scanner cin = new Scanner(System.in);
		
		n = cin.nextInt();
		k = cin.nextInt();
		
		for(i=0;i<=k;++i) flag[i] = -1;
		
		for(i=0;i< n;++i) way[i] = cin.nextInt();
		
		for(i=ans=j=0;i< n;++i){
			
			if(flag[way[i]]!=ans){
				++j;
				flag[way[i]] = ans;
			}
			
			if(j>=k){
				++ans;
				j = 0;
			}
		}
		
		System.out.println(ans+1);
	}
}

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

  2. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks