Skip to content

Instantly share code, notes, and snippets.

@ioseb
Created February 23, 2009 16:47
Show Gist options
  • Save ioseb/69049 to your computer and use it in GitHub Desktop.
Save ioseb/69049 to your computer and use it in GitHub Desktop.
package com.topcoder;
public class Bonuses {
public int[] getDivision(int[] points) {
int bonuses[] = new int[points.length];
int pool = 0, percentsLeft = 100;
for (int point : points) {
pool += point;
}
for (int i = 0; i < points.length; i++) {
bonuses[i] = (int)(points[i] / (float)pool * 100);
percentsLeft -= bonuses[i];
}
int[] sorted = new int[bonuses.length];
int[] tmp = new int[bonuses.length];
for (int i = 0; i < bonuses.length; i++) {
sorted[i] = i;
tmp[i] = bonuses[i];
}
for (int i = 0, min = 0; i < tmp.length - 1; i++) {
min = i;
for (int j = i + 1; j < tmp.length; j++) {
if (tmp[j] >= tmp[min]) {
min = j;
}
}
int k = tmp[i];
tmp[i] = tmp[min];
tmp[min] = k;
k = sorted[i];
sorted[i] = sorted[min];
sorted[min] = k;
}
for (int i = 1, v = 0, c = 0; i < sorted.length;) {
v = bonuses[sorted[i]];
while(i < sorted.length && v == bonuses[sorted[i]]) {
for (int j = i; j > c; j--) {
if (sorted[j] < sorted[j - 1]) {
int k = sorted[j];
sorted[j] = sorted[j - 1];
sorted[j - 1] = k;
}
}
i++;
}
c = i;
}
for (int i = 0; i < percentsLeft; i++) {
bonuses[sorted[i]]++;
}
return bonuses;
}
public static void main(String[] args) {
Bonuses b = new Bonuses();
int[] result = b.getDivision(new int[]{485, 324, 263, 143, 470, 292, 304, 188, 100, 254, 296, 255, 360, 231, 311, 275, 93, 463, 115, 366, 197, 470});
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + ", ");
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment