排序问题3.14

1.最小字符串 

问题描述

　　给定一些字符串(只包含小写字母)，要求将他们串起来构成一个字典序最小的字符串。

输入格式

　　第一行T,表示有T组数据。

　　接下来T组数据

　　每组第一行一个正整数n，表示字符串个数。

　　接下来n行，每行一个字符串(长度不超过100)。

输出格式

　　T行，每行一个字符串。

样例输入

1

3

a

b

c

样例输出

abc

数据规模和约定

　　T<=7000，n<=100；

 用到了functools中的cmp_to_key(cmp)来排序

 结构体排序

from functools import *
def cmp(s1, s2):
  if s1 + s2 > s2 + s1:
    return 1#换
  else:
    return -1#不换
n=int(input())
for i in range(n):
     a=[]
     t=int(input())
     for j in range(t):
          a.append(input())
     a=sorted(a,key=cmp_to_key(cmp))
     s=''.join(a)
     print(s)
           

 2.统计数字

题目描述

某次科研调查时得到了 n 个自然数，每个数均不超过 (1.5×10^9)。已知不相同的数不超过 10000 个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

输入描述

第 1 行是整数 n，表示自然数的个数。

第 2∼n 行每行一个自然数。

其中，1≤n≤2×10^5，每个数均不超过 1.5≤10^9，。

输出描述

输出 m 行（ m 为 n 个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

样例输入

8
2
4
2
4
5
100
2
100
           

样例输出

2 3
4 2
5 1
100 2            

用到了字典 

n = int(input())
nums = {}
for i in range(n):
    x = int(input())
    if x in nums.keys():
        nums[x] += 1
    else:
        nums[x] = 1
key = list(nums.keys())
key.sort()
for k in key:
    print(k, nums[k])
           

3.错误票据 （2013年省赛）

题目描述

某涉密单位下发了某种票据，并要在年终全部收回。

每张票据有唯一的 ID 号。全年所有票据的 ID 号是连续的，但 ID 的开始数码是随机选定的。

因为工作人员疏忽，在录入 ID 号的时候发生了一处错误，造成了某个 ID 断号，另外一个 ID 重号。

你的任务是通过编程，找出断号的 ID 和重号的 ID 。

假设断号不可能发生在最大和最小号。

输入描述

输入描述

要求程序首先输入一个整数 N (N<100)表示后面数据行数。

接着读入 N 行数据。

每行数据长度不等，是用空格分开的若干个（不大于 100 个），正整数（不大于10^5）。

输出描述

要求程序输出 1 行，含两个整数 m,n，用空格分隔。

其中，m 表示断号ID，n 表示重号 ID。

输入输出样例 

示例

输入

2
5 6 8 11 9
10 12 9
           

输出

7 9
           

n = int(input())
p = []
for i in range(n):
    num = input().split()
    for j in range(len(num)):
        p.append(int(num[j]))
p.sort()
a = p[0]
b = a+len(p)
for i in range(a,b):
    if i not in p:
        m = i
    if p.count(i)==2:
        n = i
print(m,n)
           

4.奖学金

结构体排序

题目描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前 5 名学生发奖学金。期末，每个学生都有 3 门课的成绩：语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的 3 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前 5 名学生的学号和总分。注意，在前 5 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据（每行输出两个数：学号、总分）是：

7 279
5 279
                
这两行数据的含义是：总分最高的两个同学的学号依次是 7 号、5 号。这两名同学的总分都是 279 （总分等于输入的语文、数学、英语三科成绩之和），但学号为 7 的学生语文成绩更高一些。如果你的前两名的输出数据是：      

5 279
7 279
           

则按输出错误处理，不能得分。

输入描述

第 1 行为一个正整数 n (6≤n≤300)，表示该校参加评选的学生人数。

第 2 到 n+1 行，每行有 3 个用空格隔开的数字，每个数字都在 0 到 100之间。第 j 行的 3 个数字依次表示学号为 j-1 的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为 1 ~ n（恰好是输入数据的行号减 1）。

所给的数据都是正确的，不必检验。

输出描述

输出共有 5 行，每行是两个用空格隔开的正整数, 依次表示前 5 名学生的学号和总分。

样例输入

6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 9
           

样例输出

6 265
4 264
3 258
2 244
1 237            

from functools import *
def cmp(a,b):
    if a[3]>b[3]:
        return 1
    if a[3]<b[3]:
        return -1
    else:
        if a[0]>b[0]:
            return 1
        if a[0]<b[0]:
            return -1
        else:
            if a[4]>b[4]:
                return 1
            else:
                return -1
n=int(input())
s=[]
for i in range(n):
    num=list(map(int,input().split()))
    b=sum(num)
    num.append(b)
    num.append(i+1)
    s.append(num)
s=sorted(s,key=cmp_to_key(cmp),reverse=True)
for i in range(5):
    print(s[i][4],s[i][3])

           

5.外卖店优先级 （2019年省赛）

题目描述

"饱了么"外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。

每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。

如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果 优先级小于等于 3，则会被清除出优先缓存。

给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优 先缓存中?

输入描述

第一行包含 3 个整数 N,M,T。

以下 M 行每行包含两个整数 ts,id，表示 ts 时刻编号 id 的外卖店收到一个订单。

其中，1≤N,M,T≤10^5，1≤ts≤T，1≤id≤N。

输出描述

输出一个整数代表答案。

输入输出样例

示例

输入

2 6 6
1 1
5 2
3 1
6 2
2 1
6 2
           

输出

1
           

1.先把各个订单按照时间排序

2.在遍历时，

a.先减去没有外卖订单时间的优先级，方法：看上一个订单的时刻，与现在时刻相减+1

b.判断优先级是否小于0，如果小于0，就让他等于0

c.判断优先级是否小于3，如果小于3，就把标记改为1

d.再让优先级+2，判断是否大于5，如果大于5，打标记

e.把这一时刻存入id的last time中

3.再重新遍历，判断是否有last time 不是最后时刻的，就让他与此时刻相减，判断是否小于3，该标记，

maxn = 100010
vis = [0] * maxn
score = [0] * maxn
last = [0] * maxn

n, m, T = list(map(int, input().split()))
a = []
for i in range(m):
    t, id = list(map(int, input().split()))
    a.append([t, id])
a = sorted(a,key=lambda s:s[0])
for every in a:
    now_time = every[0]
    now_id = every[1]

    if now_time != last[now_id]:
        score[now_id] -= (now_time - last[now_id] - 1)

    if score[now_id] < 0:
        score[now_id] = 0
    if score[now_id] <= 3:
        vis[now_id] = 0

    score[now_id] += 2
    if score[now_id] > 5:
        vis[now_id] = 1
    last[now_id] = now_time

ans = 0
for i in range(1, n + 1):
    if last[i] < T:
        score[i] -= T - last[i]
        if score[i] <= 3:
            vis[i] = 0
    ans += vis[i]
print(ans)