QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#49683#2281. BnPCTiceWA 170ms37028kbJava117.1kb2022-09-22 12:22:022022-09-22 12:22:04

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-22 12:22:04]
  • 评测
  • 测评结果:WA
  • 用时:170ms
  • 内存:37028kb
  • [2022-09-22 12:22:02]
  • 提交

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'