(UVA) Perfect Choir - Solution
Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3929
The solution below used a Greedy approach to solve this problem.
import java.io.*;
import java.util.*;
class Main {
public void process() throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while (sc.hasNext()) {
int numMembers = sc.nextInt();
int sum = 0;
int[] notes = new int[numMembers];
for (int i = 0; i < numMembers; i++) {
int note = sc.nextInt();
notes[i] = note;
sum += note;
}
int answer = 0;
if (sum%numMembers != 0) {
answer = -1;
}
else {
int desiredFinalNote = sum/numMembers;
int index = 0;
answer = 1;
while (notes[index] < desiredFinalNote) {
answer += (desiredFinalNote-notes[index]);
index++;
}
}
bw.write(answer+"\n");
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
The solution below used a Greedy approach to solve this problem.
import java.io.*;
import java.util.*;
class Main {
public void process() throws NumberFormatException, IOException {
Scanner sc = new Scanner(System.in);
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while (sc.hasNext()) {
int numMembers = sc.nextInt();
int sum = 0;
int[] notes = new int[numMembers];
for (int i = 0; i < numMembers; i++) {
int note = sc.nextInt();
notes[i] = note;
sum += note;
}
int answer = 0;
if (sum%numMembers != 0) {
answer = -1;
}
else {
int desiredFinalNote = sum/numMembers;
int index = 0;
answer = 1;
while (notes[index] < desiredFinalNote) {
answer += (desiredFinalNote-notes[index]);
index++;
}
}
bw.write(answer+"\n");
}
bw.flush();
bw.close();
return;
}
public static void main(String[] args) throws NumberFormatException, IOException {
Main m = new Main();
m.process();
System.exit(0);
}
}
Comments
Post a Comment