PIPIOJ 1142: 星球人口
题目描述
PIPI统治了N颗星球，其中第i颗星球上现在有Ai亿人口。每年每颗星球的人口都会增长K亿。从现在开始，每过100年，PIPI会挑选一颗人口最多的星球，消灭其中一半的人口。(假设当时该星球有X亿人口，将只剩下?X/2?亿人口)
请你计算现在经过了M个100年之后，这N颗星球总计还有多少亿人口。
输入
第一行包含3个整数N, M和K。
第二行包含N个整数，A1, A2, … AN。
1 <= N, M <= 100000
1 <= K <= 100
1 <= Ai <= 100000
输出
一个整数代表答案
样例输入
3 3 1
10 100 200
样例输出
735
思路
由题意很容易想到此题要用优先队列来解，直观想法是直接模拟题目所给的人口增长方式，但每次都需要维护整个优先队列，时间复杂度为o(nm)，超时。所以关键在于如何存储数据使得不需要维护整个队列。首先队列需要存储初始每个星球的人口数 x ，进一步考察题意，可以发现第 t 个 100 年时，每个星球的人口数位 y = x + 100tk，按照要求人口最多的星球人口数要减半，故为 y / 2，此时要想到若在第 t 个 100 年只需要更新人口数最多的那个星球的初始人口数据则可大大降低时间复杂度，所以列出方程 y / 2 = u + 100tk (其中 u 代表更新后人口数最多星球第 0 年的人口数，这样后续可以保证 u + 100mk 任然为第 m 个 100 年后此星球的人口数)，解得 u = x / 2 - 500tk。
735
#include<bits/stdc++.h>
using namespace std;
int main()
{int n, m, k;scanf("%d%d%d", &n, &m, &k);priority_queue<long long> q;long long ans = 0, x;for(int i = 0; i < n; i++){scanf("%lld", &x);q.push(x);}for(int i = 1; i <= m; i++){x = q.top();q.pop();q.push(x / 2 - 50 * k * i);}for(int i = 0; i < n; i++){x = q.top();q.pop();ans += (x + 100 * m * k);}printf("%lld\n", ans);return 0;
}