列表

详情

NC214728. Qingyu的暗杀名单

描述

Qingyu , M901 星系永远滴神!
传闻 Qingyu 非常记仇，有一本小本子，每当有人说出一些他不喜欢的话的时候，他总会在小本子上记上一笔，并对这个人增加一定的仇恨值，当某个人的仇恨值达到一定程度的时候，他就会永久登上 Qingyu 的暗杀名单。同样，当有人说出一些他非常喜欢的话的时候，他会给这个人减去一定的仇恨值。
Qingyu 的暗杀名单会以仇恨值从大到小排序，当仇恨值相等时，会以仇恨值增加的次数从大到小排序，如果仍然相等，会以名字的字典序从小到大排序。
根据给出的信息，请你计算 Qingyu 的暗杀名单上都有谁？

输入描述

第一行，两个整数 n 和 k，中间用一个空格隔开，表示有 n 句话会触发仇恨值的计算，当仇恨值达到 k 时会登上 Qingyu 的暗杀名单。
接下来 n 行，每行包含一个字符串 s 和一个数字 x，中间用一个空格隔开，当 x 为正表示 s 这句话 Qingyu 不喜欢，会增加 x 点仇恨值，当 x 为负表示 s 这句话 Qingyu 很喜欢，会减少 |x| 点仇恨值。
接下来一行，一个整数 m 表示有 m 个人。
以下输出 m 个人的信息。
每个人的信息中，
包含一行一个字符串 sn 表示姓名，
一行一个整数 t 表示该人说了 t 句话，
以及 t 行每行一个字符串表示说过的话 sa。
输入保证所有字符串中仅包含英文字母。

输出描述

输出共 d 行， d 表示暗杀名单上的人数。
每行包括一个字符串 sn 表示姓名和一个数字 c 表示积累的仇恨值，中间用一个空格隔开。

示例1

输入: 

3 1
tcl 1
tql -1
txdy -2
3
Vanis
2
Qingyu
tql
wkn
2
Qingyu
tcl
wyx
2
tcl
txdy

输出: 

wkn 1
wyx -1

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 384K, 提交时间: 2020-12-26 13:42:12 

#include<bits/stdc++.h>
using namespace std;

unordered_map<string,int>V;
struct node
{
	string name;
	int x,cnt;
}R[105];
bool cmp(node a,node b)
{
	if(a.x==b.x&&a.cnt==b.cnt)return a.name<b.name;
	if(a.x==b.x)return a.cnt>b.cnt;
	return a.x>b.x;
}
int main()
{
    int i,j,n,m,x,cnt,L=0;
    char T[15];
    scanf("%d%d",&n,&m);
    while(n--)scanf("%s%d",T,&i),V[T]=i;
	scanf("%d",&n);
	while(n--)
	{
		cin>>R[L].name;
		scanf("%d",&i),j=x=cnt=0;
		while(i--)
		{
			scanf("%s",T),x+=V[T];
			if(V[T]>0)cnt++;
			if(x>=m)j=1;
		}
		if(j)R[L].x=x,R[L++].cnt=cnt;
	}
	sort(R,R+L,cmp);
	for(i=0;i<L;i++)cout<<R[i].name,printf(" %d\n",R[i].x);
    return 0;
}

Python3(3.9) 解法, 执行用时: 18ms, 内存消耗: 2864K, 提交时间: 2020-12-26 15:22:33 

n, k = map(int, input().split())
a = []
table = dict()
for i in range(n):
  s, x = input().split()
  x = int(x)
  table[s] = x
m = int(input())
tot = 0
for i in range(m):
  sn = input()
  t = int(input())
  res = 0
  cnt = 0
  ok = 0
  for j in range(t):
    word = input()
    res += table.get(word, 0)
    if table.get(word, 0) > 0:
      cnt += 1
    if res >= k:
      ok = 1
  if ok:
    a.append((-res, -cnt, sn))
a.sort()
for x, y, z in a:
  print(z, -x)

pypy3(pypy3.6.1) 解法, 执行用时: 69ms, 内存消耗: 21516K, 提交时间: 2020-12-26 15:22:38 

n, k = map(int, input().split())
dic = dict()
for i in range(n):
  s, c = input().split()
  c = int(c)
  dic[s] = c
m = int(input())
res = []
for i in range(m):
  sn = input()
  t = int(input())
  ok = False
  cnt = 0
  cs = 0
  for j in range(t):
    what = input()
    cnt += dic.get(what, 0)
    if dic.get(what, 0) > 0:
      cs += 1
    if cnt >= k:
      ok = True
  if ok:
    res.append((-cnt, -cs, sn))
res.sort()
for a, b, c in res:
  print(c, -a)

上一题

© 2025 nowcoder.com