Rating

NC219917. Rating

描述

小 L 有 n 个 CF 号，每场比赛他会使用一个账号，会得到一个 Performance，假设原 Rating 为 x，Performance 为 y，则 Rating 变为 $\dfrac{x+y}{2}$ 。

小 L 会贪心地选择自己每一次使用的号，使得 每场之后 CF Rating 之和最大，请您在每一场比赛之后输出他的 Rating 之和，保留两位小数。

换句话说，每场之前，小 L 根据当前自己所有号 Rating，选出一个号参加比赛，以最大化这场之后他的 Rating 之和。下一场时，之前的选择都会被保留，即使换一种选择可能使下一场后 Rating 和更大，也不能更换之前的选择。

输入描述

第一行两个正整数 n,m，表示号的个数和比赛场数。

接下来一行 n 个整数，表示他每个号的 Rating。

之后 m 行，每行 1 个整数，表示小 L 的 Performance。

输出描述

对于每一个询问，输出一个实数表示答案，保留两位小数。

示例1

输入:

5 5
2000 2100 2200 2300 2350
1900
1500
2200
2700
2000

输出:

说明:

对于 $30\%$ 的数据， $n,m\leq 3$ 。

对于 $60\%$ 的数据， $n,m\leq 10^3$ 。

对于另外 $20\%$ 的数据， $m=1\$ 。

对于 $100\%$ 的数据， $1\leq n,m\leq 10^5$ , Rating 和 Performance 均为 $1\sim 10^5$ 之间的整数。

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

C++ 解法, 执行用时: 271ms, 内存消耗: 2684K, 提交时间: 2021-06-04 19:47:27

#include<bits/stdc++.h>
using namespace std;
priority_queue<double, vector<double>, greater<double>>q;
int n, m;
double x, y, su;
signed main() {
	cin >> n >> m;
	while (n--)
		cin >> x, q.push(x), su += x;
	while (m--)
		cin >> x, y = q.top(), q.pop(), su -= y, y = (x + y) / 2, su += y, q.push(y), printf("%.2lf\n", su);
}

pypy3 解法, 执行用时: 1016ms, 内存消耗: 54980K, 提交时间: 2021-06-04 18:56:12

import heapq

n, m = map(int, input().split())
arr = list(map(int, input().split()))
res = sum(arr)
heapq.heapify(arr)
for _ in range(m):
    p = int(input())
    s = heapq.heappop(arr)
    res -= s
    s = (s + p) / 2
    res += s
    heapq.heappush(arr, s)
    print("%.2f" % res)

Python3 解法, 执行用时: 1015ms, 内存消耗: 16272K, 提交时间: 2022-04-24 19:27:45

from heapq import *
 
n,m = map(int,input().split())
arr = list(map(int, input().split()))
ans = sum(arr)
heapify(arr)
for i in range(m):
    p = int(input())
    s = heappop(arr)
    ans -= s
    s = (s + p) / 2
    ans += s
    heappush(arr,s)
    print("%.2f" %ans)