SRM 499 DIV2
4030 ワード
250のと500のはとても简単で、言わないで、500のはとても简単で、コードは以下の通りです:
950 ptsの問題、私は少しデータ構造を考査して、データ構造を定義して、理解したいのは実はとても簡単で、コードは以下の通りです:
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;
}
}