3298. 期末预测之最佳阈值
摘要
Title: 3298. 期末预测之最佳阈值
Tag: 前缀和、思维题
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
3298. 期末预测之最佳阈值
-
题意
见原题
-
思路
统计某个数前面有多少0，后面有多少1即可
ps: 可能会出现某个数既有0状态也有1状态的情况，那么我们可以把1的排前面，也就是从大到小排
这样可以保证第一个1状态的这个数，得到的结果是最大的 -
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33'''
Author: NEFU AB-IN
Date: 2022-03-17 17:47:16
FilePath: \ACM\Acwing\3298.py
LastEditTime: 2022-03-17 17:47:17
'''
class Node():
def __init__(self, grade=0, flag=0):
self.grade = grade
self.flag = flag
n = int(input())
nums = [Node() for _ in range(n + 1)]
for i in range(1, n + 1):
nums[i].grade, nums[i].flag = map(int, input().split())
nums.sort(key = lambda x : (x.grade, -x.flag))
ans = 0
maxn = 0
for i in range(1, n + 1):
nums[i].flag += nums[i - 1].flag
cnt = 0
for i in range(1, n + 1):
sum = (i - 1) - (nums[i - 1].flag - nums[0].flag) # 加0
sum += nums[n].flag - nums[i - 1].flag #加1
if maxn <= sum:
maxn = sum
ans = nums[i].grade
print(ans)