NC24057. [USACO 2017 Jan B]Don't Be Last!
描述
Cows, being lazy creatures, don't necessarily want to be responsible for producing too much milk. If it were up to them, they would each be perfectly content to be the lowest-producing cow in the entire herd. However, they keep hearing Farmer John mentioning the phrase "farm to table" with his human friends, and while they don't quite understand what this means, they have a suspicion that it actually may not be the best idea to be the cow producing the least amount of milk. Instead, they figure it's safer to be in the position of producing the second-smallest amount of milk in the herd. Please help the cows figure out which of them currently occupies this desirable position.
输入描述
The input file for this task starts with a line containing the integer N (1≤N≤100), giving the number of entries in Farmer John's milking log.
Each of the N following lines contains the name of a cow (one of the seven above) followed by a positive integer (at most 100), indicating the amount of milk produced by the cow during one of its milking sessions.
Any cow that does not appear in the log at all is assumed to have produced no milk.
输出描述
On a single line of output, please print the name of the cow that produces the second-smallest amount of milk. More precisely, if M is the minimum total amount of milk produced by any cow, please output the name of the cow whose total production is minimal among all cows that produce more than M units of milk. If several cows tie for this designation, or if no cow has this designation (i.e., if all cows have production equal to M), please output the word "Tie". Don't forget to add a newline character at the end of your line of output. Note that M=0 if one of the seven cows is completely absent from the milking log, since this cow would have produced no milk.
示例1
输入:
10 Bessie 1 Maggie 13 Elsie 3 Elsie 4 Henrietta 4 Gertie 12 Daisy 7 Annabelle 10 Bessie 6 Henrietta 5
输出:
Henrietta
说明:
In this example, Bessie, Elsie, and Daisy all tie for the minimum by each producing 7 units of milk. The next-largest production, 9 units, is due to Henrietta.Java(javac 1.8) 解法, 执行用时: 10ms, 内存消耗: 9436K, 提交时间: 2020-12-06 11:57:59
import java.io.*;
import java.lang.reflect.Type;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
public class Main {
static class Task {
public static String roundS(double result, int scale) {
String fmt = String.format("%%.%df", scale);
return String.format(fmt, result);
// DecimalFormat df = new DecimalFormat("0.000000");
// double result = Double.parseDouble(df.format(result));
}
int rt(int x) {
if (x != fa[x]) {
int to = rt(fa[x]);
dp[x] ^= dp[fa[x]];
fa[x] = to;
return to;
}
return x;
}
void combine(int x, int y, int val) {
int rt1 = rt(x);
int rt2 = rt(y);
if (rt1 == rt2) return;
fa[rt1] = rt2;
dp[rt1] = dp[x] ^ dp[y] ^ val;
g--;
}
int fa[], dp[];
int g;
public void solve(int testNumber, InputReader in, PrintWriter out) {
// while(true) {
// int n = in.nextInt();
//
// int m =in.nextInt();
//
// fa = new int[n];
// dp = new int[n];
// for(int i=0;i<n;++i){
// fa[i] = i;
// }
// g = n;
// int c = 0;
// int as[] = new int[n];
// int bs[] = new int[n];
// char xs[] = new char[n];
//
// int at = -1;
// Set<Integer> st = new HashSet<>();
//
// for (int i = 0; i < n; ++i) {
// String line = in.next();
// int p = 0;
// int a = 0;
// while(Character.isDigit(line.charAt(p))){
// a = a*10 + (line.charAt(p)-'0'); p++;
// }
// char x = line.charAt(p++);
//
// int b = 0;
// while(p<line.length()){
// b = b*10 + (line.charAt(p)-'0'); p++;
// }
//
// as[i] = a;
// xs[i] = x;
// bs[i] = b;
//
// if(x=='='){
// int r1 = rt(a); int r2 = rt(b);
// if(r1==r2){
// if(dp[a]!=dp[b]){
// c++;
// at = i;
// }
// }else {
// combine(a, b, 0);
// }
// }else if(x=='<'){
// int r1 = rt(a); int r2 = rt(b);
// if(r1==r2){
// if(dp[a]>=dp[b]){
// c++;
// at = i;
// }
// }else {
// combine(a, b, -1);
// }
// }else{
// int r1 = rt(a); int r2 = rt(b);
// if(r1==r2){
// if(dp[a]<=dp[b]){
// c++;
// at = i;
// }
// }else {
// combine(a, b, 1);
// }
// }
//
//
// }
// if(g==1||c>=2){
// out.println("Impossible");
// continue;
// }
//
//
// for(int xuan: st){
//
//
//
//
// }
//
//
//
//
//
//
// }
String s[] =
"Bessie,Elsie,Daisy,Gertie,Annabelle,Maggie,Henrietta".split(",");
int d[] = new int[7];
int n =in.nextInt();
for(int i=0;i<n;++i){
String cf = in.next();
int p = in.nextInt();
for(int j=0;j<7;++j){
if(cf.equals(s[j])){
d[j]+= p;
break;
}
}
}
int mx = 10000000;
for(int j=0;j<7;++j){
mx = Math.min(mx,d[j]);
}
int r =100000000;
int ct= 0;
int who = -1;
for(int j=0;j<7;++j){
if(d[j]==mx) continue;
if(d[j]<r){
r = d[j]; ct =1;who = j;
}else if(d[j]==r){
ct++;
}
}
if(ct>1){
out.println("Tie");
}else if(ct==0){
out.println("Tie");
}else{
out.println(s[who]);
}
}
}
private static void solve() {
InputStream inputStream = System.in;
//InputStream inputStream = new FileInputStream(new File("D:\\chrome_download\\travel1.in"));
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task task = new Task();
task.solve(1, in, out);
out.close();
}
public static void main(String[] args) {
// new Thread(null, () -> solve(), "1", (1 << 10 ) ).start();
solve();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String nextLine() {
String line = null;
try {
line = reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
return line;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public char nextChar() {
return next().charAt(0);
}
public int[] nextArray(int n) {
int res[] = new int[n];
for (int i = 0; i < n; ++i) {
res[i] = nextInt();
}
return res;
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}
C++ 解法, 执行用时: 3ms, 内存消耗: 412K, 提交时间: 2022-06-09 07:57:06
#include <bits/stdc++.h>
using namespace std;
string solve(const map<string, int>& M) {
map<int, vector<string>> RM;
if (M.size() == 1) return begin(M)->first;
for (const auto& p : M) RM[p.second].push_back(p.first);
if (RM.size() == 1 || next(begin(RM))->second.size() > 1) return "Tie";
return next(begin(RM))->second.front();
}
int main() {
int N;
cin >> N;
map<string, int> M; // 产奶量
string s;
for (int i = 0, x; i < N; i++) cin >> s >> x, M[s] += x;
cout << solve(M) << endl;
}