srm 235 div2 1000pts

这个srm的500pts要讲一下，这题主要关键点在于要将target中的数组快速定位到离current最近的前后n个数中，纯暴力的做法是会超时的。这题还想了很久，1000pts我觉得简单，而500pts这次反而比1000pts要难。

看500pts的代码：

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class StepperMotor {
   public int rotateToNearest(int n, int current, int[] target) {
		long step=Long.MAX_VALUE;
		for(int tar:target){
			long temStep=getStep(tar,current,n);
			if(Math.abs(temStep)<Math.abs(step)){
					step=temStep;	
			}else if(Math.abs(temStep)==Math.abs(step)){
					if(temStep>step){
						step=temStep;
					}
			}
		}
		
		return (int)step;
   }
   
   public long getStep(long tar,long current,long n){
   		if(tar>=current){
   			long gap=tar-current;
   			tar=tar-gap/n*n;
  			long t1=tar-current;
  			long t3=current-(tar-n);
   			if(t1<=t3)
   				return t1;
   			else
   				return -1*t3;	
   		}else{
				long gap=current-tar;
				tar=tar+gap/n*n;   		
				long t1=current-tar;
				long t3=tar+n-current;
				if(t3<=t1)
					return t3;
				else
					return -1*t1;
   		}		
   }
}

至于1000pts，主要是数据结构的问题，理解了挺简单的。不过注意一点，如A B A三篇文章的话，如果B引用了0，2文章，则实际上A要计数两次的，一开始这地方没注意到，wa了一次。
代码如下：

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class AcademicJournal {
   public String[] rankByImpact(String[] papers) {
		String[] ans=null;
		Vector<Arr> hm=new Vector<Arr>();
		
		for(String s:papers){
			String s1[]=s.split("\\.");
			HashSet<Integer> vec=new HashSet<Integer>();
			hm.add(new Arr(s1[0],vec));
			if(s1.length>1){
				String s2[]=s1[1].trim().split(" ");
				for(String t:s2)
					vec.add(Integer.parseInt(t));
			}//if
		}//for
		
		HashMap<String,Jour> ps=new HashMap<String,Jour>();
		for(int j=0;j<hm.size();j++){
			Arr arr=hm.get(j);
			String name=arr.name;
			Jour jour=ps.get(name);
			if(jour==null){
				jour=new Jour();
				jour.name=name;
				ps.put(name,jour);
			}
			jour.addPaper(j+"");
			
			HashSet<Integer> vec=arr.vec;
			for(int i:vec){
				String otherJour=hm.get(i).name;
				Jour otherJ=ps.get(otherJour);
				if(otherJ==null){
					otherJ=new Jour();
					otherJ.name=otherJour;
					ps.put(otherJour,otherJ);	
				}
				if(!name.equals(otherJour)){
					otherJ.citaCount++;
				}
			}//for
		}//for
		
		Jour jours[]=ps.values().toArray(new Jour[0]);
		for(Jour jour:jours){
			jour.caluRank();
		}
		Arrays.sort(jours);
		ans=new String[jours.length];
		for(int i=0;i<jours.length;i++){
			ans[i]=jours[i].name;
		}
		
		return ans;
   }
   
   class Arr{
   	String name;
   	HashSet<Integer> vec;
   	public Arr(String name,HashSet<Integer> vec){
   		this.name=name;
   		this.vec=vec;
   	}
   }
   
   class Jour implements Comparable<Jour>{
   		double rank;
   		String name=null;
   		int citaCount;
   		HashSet<String> papers=new HashSet<String>();
   		
   		public int compareTo(Jour jour){
   			if(rank<jour.rank)
   				return 1;
   			if(rank>jour.rank)
   				return -1;	
   			
   			if(papers.size()>jour.papers.size())
   				return -1;
   			if(papers.size()<jour.papers.size())
   				return 1;
   				
   			return name.compareTo(jour.name);		
   		}
   		
   		public void addPaper(String paper){
   			papers.add(paper);
   		}
   		
   		public void caluRank(){
   				rank=citaCount/(double)papers.size();
   		}
   }
}