NOIP2016 day2 t2 蚯蚓

干物国大皇帝 · 2019-02-15 11:30:25 · 题解

NOIP2016 day2 t2 蚯蚓

“这题有一种广为人知的做法，它叫优先队列。” ——干物国大皇帝

嗯……感觉像个模拟。

用sum将蚯蚓的总增长计算出来，因为蚯蚓们的增长相同所以不会影响排位，也能更方便操作。
这题输出有点大（随便看了一个点，有1M多），强烈推荐使用 快读快输（顺带一提，code中的快输是自适应型，不用改数据类型，可以图个方便）。
此题还要注意一下，什么时候保留小数，什么时候取整。

~~朕的代码一向可读性较高~~，看不懂的可以在聊天栏里冒泡。如有更好的方法（简洁+高效），欢迎众帅卿靓臣上疏直谏

//没抢到Bilibili今年的拜年祭手办，心碎pianggang……

65分：优先队列

（洛谷上数据好像有点水，测出来85分，官方数据是65分）

#include<bits/stdc++.h>
using namespace std;

#define il inline

double p;
int sum;//蚯蚓总增长 
int n, m, k/*q*/, u, v, t;
priority_queue<int> q;//优先队列 

il int read()  {
  int x=0;  bool f=1;  char ch=getchar();
  while(ch<48||ch>57)  { if(ch=='-') f=0;  ch=getchar(); }
  while(ch>=48&&ch<=57)  { x=(x<<3)+(x<<1)+(ch^48);  ch=getchar(); }
  return f?x:-x;
}
template<typename T> void print(const T x)  {
  if(x >= 10)  print(x/10);
  putchar( (x%10)|48 ); 
}
template<typename T>il void put(const T x)  {
  if(x < 0)  putchar('-'), print(-x);
  else  print(x);
}


int main()  {
  freopen("input1.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);

  n=read(), m=read(), k=read(), u=read(), v=read(), t=read();
  p = (double)u/v;//不要掉精度
  for(int i = 0; i < n; ++i)  {
    int a;
    a=read();
    q.push(a);
  }
  for(int i = 1; i <= m; ++i)  {
    int l = q.top()+sum;//被切的蚯蚓的长度
    if(i%t == 0)  put(l), putchar(' ');/* 输出第一排 */
    q.pop();
    sum += k;
    int nl = l*p;
    q.push(nl-sum);
    q.push(l-nl-sum); 
  }
  printf("\n");
  int tim = 0;
  while( !q.empty() )  {
    tim++;
    int l = q.top()+sum;
    if(tim%t == 0)  put(l), putchar(' ');
    q.pop();
  }

  return 0;
}

100分：手工队列

优先队列不够快，会TLE！！

仔细想想，就能发现先被切掉的蚯蚓分成的蚯蚓一定比后切掉的蚯蚓分成的蚯蚓长，这就是题目中隐含的单调性。那么蚯蚓有如下三种状态：

q：没切的；
q1：切了的；
q2：切剩下的。

由此可得：每个模拟队列的第一个值（q[0], q1[0], q2[0]）都为该队列中最大。

如此这般，用DIY的手工队列替换优先队列即可。

#include<bits/stdc++.h>
using namespace std;

#define il inline

const int N = 1e5+5, M = 7e6+5;
const int inf = 0x3f3f3f3f;
double p;
int sum;
int n, m, k, u, v, t;
int q[N], q1[M], q2[M], head, head1, head2, tail, tail1, tail2;//手工队列 

il int read()  {
  int x=0;  bool f=1;  char ch=getchar();
  while(ch<48||ch>57)  { if(ch=='-') f=0;  ch=getchar(); }
  while(ch>=48&&ch<=57)  { x=(x<<3)+(x<<1)+(ch^48);  ch=getchar(); }
  return f?x:-x;
}
template<typename T> void print(const T x)  {
  if(x >= 10)  print(x/10);
  putchar( (x%10)|48 ); 
}
template<typename T>il void put(const T x)  {
  if(x < 0)  putchar('-'), print(-x);
  else  print(x);
}


il bool cmp(int a, int b)  { return a > b; }


il int TOP()  {//相当于 q.top() 
  int x=-inf, x1=-inf, x2=-inf;
  if(head < tail)  x = q[head];
  if(head1 < tail1)  x1 = q1[head1];
  if(head2 < tail2)  x2 = q2[head2];
  if(x>=x1 && x>x2)  { head++;  return x; }//x最大 
  else if(x1 > x2)  { head1++;  return x1; }//x1最大 
  head2++;  return x2;//x2最大 
}


int main()  {
  n=read(), m=read(), k=read(), u=read(), v=read(), t=read();
  p = (double)u/v;//浮点数精度不要丢 
  tail = n;
  for(int i = 0; i < n; ++i)  q[i]=read();
  sort(q, q+n, cmp);//优先性 
  //q, q1, q2都是0基准
  for(int i = 1; i <= m; ++i)  {
    int x = TOP()+sum;
    if(i%t == 0)  put(x), putchar(' ');
    sum += k;
    int nx = p*x;
    int x1 = nx-sum, x2 = x-nx-sum;
    q1[tail1++]=x1, q2[tail2++]=x2;
  }
  putchar('\n');
  int tim = 0;
  while( ++tim<=(n+m) )
    if(tim%t == 0)  put(TOP()+sum), putchar(' ');
    else  TOP();//出队=q.pop() 

  return 0;
}