Topcoder Single Round Match 561
Problem Statement
You are organizing a subregional ACM ICPC contest. The problemset at the contest will consist of M problems. According to an ACM ICPC tradition, when a team solves a problem, it gets awarded a balloon. To account for this, you've bought balloons of N different colors (conveniently numbered from 0 to N-1). The number of balloons of color i that you've bought is given by balloonCount[i]. Balloons come in two sizes: medium and large. All balloons of the same color have the same size. If the i-th character of balloonSize is 'M', then all balloons of color i have medium size, and if this character is 'L', then all balloons of color i have large size.
Today you've been at the meeting with the scientific committee of the contest. There, you learned that there are additional restrictions of which you were not aware. Here are those restrictions:
All balloons that get awarded for a particular problem must have the same color and size.
For any two problems, the colors of balloons awarded for solving them must be different. In other words, the color of balloons awarded for each problem must be unique.
These are definitely bad news, since you ordered balloons pretty much arbitrarily and it's possible that you won't be able to satisfy the restrictions with the balloons you currently have. However, the good news is that scientific committee members were able to evaluate the difficulty of each problem. More exactly, they told you that the maximum number of teams that can potentially solve the i-th problem is maxAccepted[i]. The scientific committee members are very clever and experienced, so their prediction is guaranteed to come true.
Your budget is limited and balloons are expensive, so buying more of them is not an option. Fortunately, there is a very cheap balloon repaint service at your city, so you are going to use it. The service offers repainting a given balloon into any other color. This can be one of the N colors you have, as well as any color that you don't have yet. However, it is not possible to change the size of a balloon.
You are given the int[]s balloonCount, maxAccepted and the String balloonSize. Return the minimum number of balloons that have to be repainted in order to guarantee that you will be able to award balloons to the teams properly. If it is impossible to achieve the goal using any number of balloon repaintings, return -1.
Definition
Class: ICPCBalloons
Method: minRepaintings
Parameters: int[], String, int[]
Returns: int
Method signature: int minRepaintings(int[] balloonCount, String balloonSize, int[] maxAccepted)
(be sure your method is public)
Constraints
- balloonCount will contain between 1 and 50 elements, inclusive.
- Each element of balloonCount will be between 1 and 100, inclusive.
- balloonSize will contain the same number of characters as the number of elements in balloonCount.
- Each character of balloonSize will be 'M' or 'L'.
- maxAccepted will contain between 1 and 15 elements, inclusive.
- Each element of maxAccepted will be between 1 and 100, inclusive.
Java代码：
/*
*SRM561_DIV2_500pts
*/
import java.util.ArrayList;
import java.util.Collections;
public class ICPCBalloons {
public static void main (String args[]) {
int[] balloonCount = {1,3,5,2,4,7,9,8};
String balloonSize = "MLMLMLML";
int[] maxAccepted = {3,5,7,9,10};
ICPCBalloons obj = new ICPCBalloons();
int ans = obj.minRepaintings(balloonCount, balloonSize, maxAccepted);
System.out.println(ans);
}
public int calc(ArrayList need, ArrayList actual) {
if (need == null || actual == null)
return -1;
int nSize = need.size();
int aSize = actual.size();
int mSize = Math.max(nSize, aSize);
int sum = 0;
for (int i = 0; i < mSize; i++) {
int needEle = i < nSize ? need.get(i) : 0;
int actualEle = i < aSize ? actual.get(i) : 0;
sum += needEle > actualEle ? (needEle - actualEle) : 0;
}
return sum;
}
public int minRepaintings(int[] balloonCount, String balloonSize, int[] maxAccepted) {
ArrayList mbList = new ArrayList();
ArrayList lbList = new ArrayList();
int total = maxAccepted.length;
int ans = Integer.MAX_VALUE;
int totalM = 0, totalL = 0;
int colors = balloonCount.length;
for (int i = 0; i < colors; i++) {
if (balloonSize.charAt(i) == 'M') {
mbList.add(balloonCount[i]);
totalM += balloonCount[i];
} else {
lbList.add(balloonCount[i]);
totalL += balloonCount[i];
}
}
Collections.sort(mbList,Collections.reverseOrder());
Collections.sort(lbList,Collections.reverseOrder());
for (int i = 1; i <= 1 << total; i++) {
int needM = 0;
int needL = 0;
ArrayList umList = new ArrayList();
ArrayList ulList = new ArrayList();
for (int j = 0; j < total; j++) {
if (((i >> j) & 1) == 1) {
umList.add(maxAccepted[j]);
needM += maxAccepted[j];
} else {
ulList.add(maxAccepted[j]);
needL += maxAccepted[j];
}
}
if (needL > totalL || needM > totalM)
continue;
Collections.sort(umList,Collections.reverseOrder());
Collections.sort(ulList,Collections.reverseOrder());
int resM = calc(umList,mbList) + calc(ulList,lbList);
if (resM < ans)
ans = resM;
}
if (ans != Integer.MAX_VALUE)
return ans;
return -1;
}
}
本文链接：http://bookshadow.com/weblog/2014/05/11/topcoder-srm-561-icpc-balloons/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
