难点: delta 与 q的关系, 琢磨了好久, 才发现最后输出要加delta, 明白了, 但是自己写,不可能的。。。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 7e6+5;
int n, m, q, u, v, t;
int q1[maxn],q2[maxn],q3[maxn];
int head_q1, head_q2, head_q3, rear_q1, rear_q2=-1, rear_q3=-1;
int delta;
int get_max() //得到三个队列里面的最大值,
{
int x = INT_MIN;
if(head_q1 <= rear_q1) x = max(x, q1[head_q1]);
if(head_q2 <= rear_q2) x = max(x, q2[head_q2]);
if(head_q3 <= rear_q3) x = max(x, q3[head_q3]); //这三个队列如果有数,则与最大的数比较,得到最大的
if(head_q1 <= rear_q1&&x == q1[head_q1]) head_q1 ++; //如果最大数取在第一个队列,则第一个队列头++,就是去除第一个数
else
if(head_q2 <= rear_q2&&x == q2[head_q2]) head_q2 ++;
else
head_q3 ++;
return x;
}
int main()
{
scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
for(int i = 0; i < n; i ++)
{
scanf("%d",&q1[i]);
}
sort(q1,q1 + n);
reverse(q1,q1 + n); //反转一下,从大到小
rear_q1 = n-1;
for(int i = 1; i <= m; i ++)
{
int x = get_max();
x += delta; //这个delta 与下面的q 我说不清楚,得自己琢磨
int l = x * 1ll * u / v; //求分开扣左边的数字
int r = x - l; //右边的数字
delta += q;
if(i % t == 0) printf("%d ",x); //输出第t,2t。。。最大值
q2[++ rear_q2] = l - delta; //这里自己想想 好难啊啊啊啊啊啊
q3[++ rear_q3] = r - delta;
}
puts("");
for(int i = 1; i <= m+n; i ++)
{
int x = get_max();
if(i%t == 0) printf("%d ",x+delta); //得到最大值排序,然后输出,delta就是特别神奇的加上去了
}
puts("");//相当于换行
return 0;
}