dshao3@asu.edu
BAN USERint id5207197178920960(int[] array, int target){
int[][] dp = new int[array.length][101];
for(int i=1;i<=100;i++){
dp[0][i] = Math.abs(array[0]-i);
}
for(int i=1;i<array.length;i++){
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
for(int i=1;i<array.length;i++){
for(int j=1;j<=100;j++){
for(int k=Math.max(j-target, 1);k<=Math.min(j+target, 100);k++){
dp[i][j] = Math.min(dp[i][j], dp[i-1][k]+Math.abs(j-array[i]));
}
}
}
int res = Integer.MAX_VALUE;
for(int i=1;i<=100;i++){
res = Math.min(res, dp[array.length-1][i]);
}
return res;
}
public class id5649103830646784 {
public static void main(String arcg[]){
id5649103830646784 h = new id5649103830646784();
int[] array = {33,25,26,58,41,59};
pair[] array2 = new pair[array.length];
for(int i=0;i<array.length;i++){
array2[i] = h.new pair(array[i]);
}
h.sort(array2);
for(int i=0;i<array2.length;i++){
System.out.println(array2[i].val + ": " + array2[i].qaz);
}
}
class pair{
int val;
int qaz;
public pair(int val){
this.val = val;
qaz = 0;
}
}
private pair[] array;
private pair[] helper;
void sort(pair[] array){
this.array = array;
this.helper = new pair[array.length];
mergeSort(0,array.length-1);
}
void mergeSort(int low, int high){
if(low < high){
int mid = low+(high-low)/2;
mergeSort(low, mid);
mergeSort(mid+1, high);
merge(low,mid,high);
}
}
void merge(int low, int mid, int high){
for(int i=low;i<=high;i++) helper[i] = array[i];
int i=low, j=mid+1,k=low;
while(i<=mid && j<=high){
if(helper[i].val<=helper[j].val){
array[k] = helper[i++];
array[k].qaz += high-j+1;
}
else{
array[k] = helper[j++];
}
k++;
}
while(i<=mid) array[k++] = helper[i++];
}
}
void id5186461135536128(int[] array, int n){
Map<Integer,Integer> map = new HashMap<Integer, Integer>();
int range = 0;
for(int i:array){
if(!map.containsKey(i))
map.put(i, 1);
else
map.put(i, map.get(i)+1);
range = Math.max(range, map.get(i));
}
int[] count = new int[range+1];
for(Map.Entry<Integer, Integer> entry:map.entrySet()){
count[entry.getValue()]++;
}
for(int i=1;i<count.length;i++){
count[i] += count[i-1];
}
Entry[] res = new Entry[map.size()];
for(Map.Entry<Integer, Integer> entry:map.entrySet()){
res[--count[entry.getValue()]] = entry;
}
for(int i=res.length-1;i>res.length-1-n;i--){
System.out.println(res[i].getKey());
}
}
- dshao3@asu.edu June 23, 2015