SRM 499 DIV2

4030 ワード

250のと500のはとても简単で、言わないで、500のはとても简単で、コードは以下の通りです:

import java.util.Arrays;

public class ColorfulRabbits {

	//easy problem!
	public int getMinimum(int[] replies) {
		int ans=0;
		
		Arrays.sort(replies);
		int n=replies.length;
		for(int i=0;i<n;){
			int count=replies[i];
			int j=0;
			for(;j<count+1&&i+j<n;j++){
				if(replies[i+j]!=count){
					break;
				}
			}
			
			i+=j;
			ans+=count+1;
		}
		
		return ans;
	}

}

950 ptsの問題、私は少しデータ構造を考査して、データ構造を定義して、理解したいのは実はとても簡単で、コードは以下の通りです:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Vector;

public class PalindromeGame {

	public int getMaximum(String[] front, int[] back) {
		HashMap<String,FrontBack> hm=new HashMap<String,FrontBack>();
		int n=front.length;
		for(int i=0;i<n;i++){
			String f=front[i];
			int b=back[i];
			Node node=new Node(f,b);
			StringBuffer sb=new StringBuffer(f);
			FrontBack matched=hm.get(f);
			if(matched==null){
				matched=hm.get(sb.reverse().toString());
			}
			if(matched ==null){
				FrontBack frontBack=new FrontBack();
				frontBack.mark=f;
				frontBack.isPalmeString=isPalmeString(f);
				matched=frontBack;
				hm.put(f, frontBack);
			}
			matched.add(node);
		}//for
		
		int ans=0;
		Vector<Integer> vec=new Vector<Integer>();
		FrontBack frontBacks[]=hm.values().toArray(new FrontBack[0]);
		for(FrontBack fb:frontBacks){
			Node nodes1[] = fb.queue1.toArray(new Node[0]);
			Node nodes2[] = fb.queue2.toArray(new Node[0]);
			Arrays.sort(nodes1);
			Arrays.sort(nodes2);
			if(fb.isPalmeString){
				if(nodes1.length%2==0){
					for(Node node:nodes1)
						ans+=node.back;
				}else{
					for(int i=0;i<nodes1.length-1;i++){
						ans+=nodes1[i].back;
					}
					vec.add(nodes1[nodes1.length-1].back);
				}
				
				if(nodes2.length%2==0){
					for(Node node:nodes2)
						ans+=node.back;
				}else{
					for(int i=0;i<nodes2.length-1;i++){
						ans+=nodes2[i].back;
					}
					vec.add(nodes2[nodes2.length-1].back);
				}
			}else{
				int min = Math.min(nodes1.length, nodes2.length);
				for (int i = 0; i < min; i++) {
					ans += nodes1[i].back + nodes2[i].back;
				}
			}
		}//for
		
		Integer[] ins=vec.toArray(new Integer[0]);
		Arrays.sort(ins);
		if(ins!=null&&ins.length>0){
			return ans+ins[ins.length-1];
		}else{
			return ans;
		}
	}

	public boolean isPalmeString(String str){
		char[] chs=str.toCharArray();
		int n=chs.length;
		for(int i=0;i<n/2;i++){
			if(chs[i]!=chs[n-1-i])
				return false;
		}
		
		return true;
	}
}

class FrontBack{
	ArrayList<Node> queue1=new ArrayList<Node>();
	ArrayList<Node> queue2=new ArrayList<Node>();
	String mark=null;
	boolean isPalmeString=false;
	
	public void add(Node node){
		if(mark.equals(node.front)){
			queue1.add(node);
		}else{
			queue2.add(node);
		}
	}
}

class Node implements Comparable<Node>{

	String front=null;
	int back=-1;
	
	public Node(String front, int back) {
		super();
		this.front = front;
		this.back = back;
	}

	public int compareTo(Node node) {
		if(back>node.back)
			return -1;
		
		if(back<node.back)
			return 1;
		
		return 0;
	}
}