QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#49683 | #2281. BnPC | Tice | WA | 170ms | 37028kb | Java11 | 7.1kb | 2022-09-22 12:22:02 | 2022-09-22 12:22:04 |
Judging History
answer
import java.io.*;
import java.util.*;
import java.util.Map.Entry;
public class BnPC {
private static int points;
private static HashMap<String, Integer> attributePoints = new HashMap<>();
private static HashMap<String, HashMap<String, Integer>> attributeEventsInfo = new HashMap<>();
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int total = 0;
String[] input = in.readLine().split(" ");
points = Integer.parseInt(input[1]);
for (int i = 0; i < Integer.parseInt(input[0]); i++) {
String[] attribute = in.readLine().split(" ");
attributePoints.put(attribute[0], Integer.parseInt(attribute[1]));
HashMap<String, Integer> attributeEventInfo = new HashMap<>();
attributeEventInfo.put("amount", 0);
attributeEventInfo.put("highest", 0);
attributeEventInfo.put("amountHighest", 0);
attributeEventsInfo.put(attribute[0], attributeEventInfo);
}
int eventAmount = Integer.parseInt(in.readLine());
for (int i = 0; i < eventAmount; i++) {
String[] event = in.readLine().split(" ");
HashMap<String, Integer> eventMap = attributeEventsInfo.get(event[0]);
eventMap.put("amount", eventMap.get("amount") + 1);
int threshold = Integer.parseInt(event[1]);
if (threshold > attributeEventsInfo.get(event[0]).get("highest")) {
eventMap.put("highest", threshold);
eventMap.put("amountHighest", 1);
if (threshold > attributePoints.get(event[0])) {
points -= threshold - attributePoints.get(event[0]);
attributePoints.put(event[0], threshold);
}
} else if (threshold == attributeEventsInfo.get(event[0]).get("highest")) {
eventMap.put("amountHighest", eventMap.get("amountHighest") + 1);
}
}
// for (int i = 0; i < points; i++) {
// String bestAttr = "";
// int bestImpact = 0;
// for (String currentAttr : attributePoints.keySet()) {
// int amount = attributeEventsInfo.get(currentAttr).get("amount");
// int amountHighest = attributeEventsInfo.get(currentAttr).get("amountHighest");
// int score = attributePoints.get(currentAttr) ;
// if (attributePoints.get(currentAttr) == (attributeEventsInfo.get(currentAttr).get("highest"))) {
// int impact = score * amountHighest + amount;
// if (impact > bestImpact) {
// bestAttr = currentAttr;
// bestImpact = impact;
// }
// } else {
// if (amount > bestImpact) {
// bestAttr = currentAttr;
// bestImpact = amount;
// }
// }
// }
// attributePoints.put(bestAttr, attributePoints.get(bestAttr) + 1);
// }
// int mostOccurring = 0;
// String mostName = "";
// int events = attributeEventsInfo.size();
// ArrayList<String> totalsNames = new ArrayList<>();
// ArrayList<Integer> totalImpacts = new ArrayList<>();
// for (Entry<String, HashMap<String, Integer>> entry : attributeEventsInfo.entrySet()) {
// int amount = entry.getValue().get("amount");
// int amountHighest = entry.getValue().get("amountHighest");
// int score = attributePoints.get(entry.getKey());
// int impact = score * amountHighest + amount;
// totalsNames.add(entry.getKey());
// totalImpacts.add(impact);
// if (amount > mostOccurring) {
// mostOccurring = amount;
// mostName = entry.getKey();
// }
// }
//
// List[] sorted = sortTotals(new List[]{totalsNames, totalImpacts});
// totalsNames = (ArrayList<String>) sorted[0];
// totalImpacts = (ArrayList<Integer>) sorted[1];
//
// for (int i = 0; i < totalImpacts.size(); i++) {
// if (points <= 0) break;
// if (mostOccurring < totalImpacts.get(i)) {
// attributePoints.put(totalsNames.get(i), attributePoints.get(totalsNames.get(i)) + 1);
// points--;
// } else {
// attributePoints.put(mostName, attributePoints.get(mostName) + points);
// points = 0;
// }
// }
//
// attributePoints.put(mostName, attributePoints.get(mostName) + points);
ArrayList<Attribute> impacts = new ArrayList<>();
String highestAmountName = "";
int highestAmount = 0;
for (String currentAttr : attributePoints.keySet()) {
int amount = attributeEventsInfo.get(currentAttr).get("amount");
if (amount > highestAmount) {
highestAmountName = currentAttr;
highestAmount = amount;
}
int amountHighest = attributeEventsInfo.get(currentAttr).get("amountHighest");
int score = attributePoints.get(currentAttr);
int impact = score * amountHighest + amount;
impacts.add(new Attribute(currentAttr, impact));
}
impacts = sortTotals(impacts);
for (Attribute attribute : impacts) {
if (points <= 0) break;
if (highestAmount < attribute.getPoints()) {
attributePoints.put(attribute.getName(), attributePoints.get(attribute.getName()) + 1);
points--;
} else {
attributePoints.put(highestAmountName, attributePoints.get(highestAmountName) + points);
points = 0;
}
}
System.out.println(totalPoints());
}
private static int totalPoints() {
int total = 0;
for (Entry<String, Integer> entry : attributePoints.entrySet()) {
HashMap<String, Integer> currentAttribute = attributeEventsInfo.get(entry.getKey());
int attributeScore = entry.getValue();
if (attributeScore == currentAttribute.get("highest")) {
total += (currentAttribute.get("amount") - currentAttribute.get("amountHighest")) * attributeScore;
} else if (attributeScore > currentAttribute.get("highest")) {
total += currentAttribute.get("amount") * attributeScore;
}
}
return total;
}
private static ArrayList<Attribute> sortTotals(List in) {
ArrayList<Attribute> list = new ArrayList<Attribute>(in);
if (list.size() <= 1) return list;
ArrayList<Attribute> firstHalf = (ArrayList<Attribute>) sortTotals(list.subList(0, list.size()/2));
ArrayList<Attribute> secondHalf = (ArrayList<Attribute>) sortTotals(list.subList(list.size()/2, list.size()));
ArrayList<Attribute> result = new ArrayList<>();
int i = 0, n = 0;
while (i < firstHalf.size() && n < secondHalf.size()) {
if (firstHalf.get(i).getPoints() > secondHalf.get(i).getPoints()) {
result.add(new Attribute(firstHalf.get(i).getName(), firstHalf.get(i).getPoints()));
i++;
} else {
result.add(new Attribute(secondHalf.get(n).getName(), secondHalf.get(n).getPoints()));
n++;
}
}
while (i < firstHalf.size()) {
result.add(new Attribute(firstHalf.get(i).getName(), firstHalf.get(i).getPoints()));
i++;
}
while (n < secondHalf.size()) {
result.add(new Attribute(secondHalf.get(n).getName(), secondHalf.get(n).getPoints()));
n++;
}
return result;
}
}
class Attribute {
String name;
Integer points;
public Attribute(String name, Integer points) {
this.name = name;
this.points = points;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Integer getPoints() {
return points;
}
public void setPoints(Integer points) {
this.points = points;
}
public String toString() {
return "{name: " + name + "; points: " + points+ ";}";
}
}
详细
Test #1:
score: 100
Accepted
time: 115ms
memory: 36104kb
input:
3 14 THISISTHEONE 8 B 0 C 0 8 THISISTHEONE 10 C 0 B 1 B 0 THISISTHEONE 0 C 1 THISISTHEONE 0 THISISTHEONE 0
output:
82
result:
ok single line: '82'
Test #2:
score: 0
Accepted
time: 159ms
memory: 36164kb
input:
3 99 THEFIRSTINCREASE 6 SECONDINCREASE 4 ZZZ 1 9 THEFIRSTINCREASE 4 ZZZ 0 THEFIRSTINCREASE 6 SECONDINCREASE 8 THEFIRSTINCREASE 2 SECONDINCREASE 1 ZZZ 0 SECONDINCREASE 8 THEFIRSTINCREASE 3
output:
429
result:
ok single line: '429'
Test #3:
score: -100
Wrong Answer
time: 170ms
memory: 37028kb
input:
5 20 A 100 B 200 C 300 D 400 E 500 949 A 39 A 23 C 163 A 98 B 36 A 3 A 52 B 152 B 167 B 65 C 142 B 66 B 117 C 288 C 155 E 341 A 97 D 173 E 31 A 62 D 90 E 361 A 42 D 85 E 1 C 141 B 77 B 194 D 221 E 203 D 345 E 48 B 26 D 46 B 74 E 380 B 181 C 243 B 112 A 99 E 403 C 20 E 453 C 149 B 26 E 245 A 74 D 304...
output:
282149
result:
wrong answer 1st lines differ - expected: '285180', found: '282149'