原题链接:https://www.luogu.com.cn/problem/P2827
题意解读:初始n个数,每次取最大值x,根据u/v分成两部分:x * u / v,x - x * u / v,然后其余数都增加q,整个过程重复m次。
输出有两类数据:第t,2t,3t...次取出的最大值;最后剩余的数第t,2t,3t...个,从大到小输出。
解题思路:
直观上,通过模拟法可以实现本题,要每次取最大值,可以借助优先队列。
但是,问题在于,每次如果把剩余数都增加q,意味着每次都有O(n)的复杂度,最终复杂度为O(m * n)。
转念一想,把剩余数增加q,可以变成把切断的两个数都减去q,其余数不变,然后记录这个累加值,后面再进行还原即可。
分析一下复杂度,超过O(m * log n) , 7*10^6*log(100000) 仍然会超过10^8,可以得到部分分。
85分代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, q, u, v, t;
priority_queue<ll> pq;
int main()
{
cin >> n >> m >> q >> u >> v >> t;
int x;
int add = 0; //每个数都应该增加值
while(n--)
{
cin >> x;
pq.push(x);
}
for(int i = 1; i <= m; i++)
{
//从优先队列取最大值,并还原应该的值
ll mx = pq.top() + add;
if(i % t == 0) cout << mx << " ";
pq.pop();
//将mx分成两部分
ll part1 = mx * u / v;
ll part2 = mx - part1;
//其余部分增加q相当于将part1、part2减去q,还要减去累计的值add
part1 = part1 - q - add;
part2 = part2 - q - add;
//将part1,part2加入优先队列
pq.push(part1);
pq.push(part2);
add += q; //每个数都应该增加的值+q
}
cout << endl;
int i = 0;
while(pq.size())
{
if(++i % t == 0) cout << pq.top() + add << " ";
pq.pop();
}
return 0;
}
如何进一步优化?不难分析,每次取最大数分成两部分,得到的较小的数、较大的数一定分别都是单调不增的,那么就没必要维护优先队列,
只需要定义三个队列q0,q1,q2,q0来保存原始数由大到小排序,q1保存每次拆分后的较小值,q2保存每次拆分后的较大值,这样q0,q1,q2都能保证是从大到小排序,每次取最大数时,只需要比较三个队列头,取最大的那一个即可。
时间复杂度就降为O(m)。
100分代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
int n, m, q, u, v, t;
ll a[N]; //蚯蚓长度
queue<ll> que[3]; //que[0]存蚯蚓长度从大到小,que[1]存切后较小长度,que[2]存切后较大长度
int main()
{
cin >> n >> m >> q >> u >> v >> t;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1, greater<int>());
for(int i = 1; i <= n; i++) que[0].push(a[i]);
int add = 0; //每个数都应该增加值
for(int i = 1; i <= m; i++)
{
int maxn = 0;
ll maxx = LLONG_MIN;
for(int j = 0; j < 3; j++)
{
if(que[j].size() && que[j].front() > maxx)
{
maxn = j;
maxx = que[j].front();
}
}
que[maxn].pop();
maxx += add; //还原本来值
if(i % t == 0) cout << maxx << " ";
//将maxx切成两部分
ll part1 = maxx * u / v;
ll part2 = maxx - part1;
//其余部分增加q相当于将part1、part2减去q,还要减去累计的值add
part1 = part1 - q - add;
part2 = part2 - q - add;
//短的加入que[1],保证que[1]是单调递减
que[1].push(part1);
//长度加入que[2],保证que[2]是单调递减
que[2].push(part2);
//每个数要增加值更新
add += q;
}
cout << endl;
for(int i = 1; i <= n + m; i++)
{
int maxn = 0;
ll maxx = LLONG_MIN;
for(int j = 0; j < 3; j++)
{
if(que[j].size() && que[j].front() > maxx)
{
maxn = j;
maxx = que[j].front();
}
}
que[maxn].pop();
if(i % t == 0) cout << maxx + add << " ";
}
return 0;
}
标签:NOIP2016,maxx,int,洛谷题,P2827,每次,数都,que,复杂度 From: https://www.cnblogs.com/jcwy/p/18532431