目录

• 蚯蚓

由于我太懒了呀，再加上最近天天考试，就合起来写吧。（长期更新（CSP前））。

蚯蚓

noip2016 提高组day2 t2

题目

题意：

给定n条蚯蚓，接下来的m秒钟的时间里每秒将最长的蚯蚓切成⌊px⌋和x-⌊px⌋（0<p<1），其余蚯蚓则增长p，每t秒输出一次本次切割的蚯蚓的原长，最后将所得蚯蚓从大到小排序后输出第t、2t、3t……的蚯蚓的长度。ps：切割所得的长度为0的蚯蚓也需要保留

难度：中等

思路:

[60分做法]：

根据数据范围，有12个点的q为0，即蚯蚓不会增长，那么只需用优先队列将所有的蚯蚓存入，每次取出队首，切割完再放回即可。

Code：

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
//Mystery_Sky
//预计->60
#define M 200010
#define INF 0x3f3f3f3f
#define ll long long
inline int read()
{
    int x=0,f=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}
int n, m, q, u, v, t;
double p;
int a[M];
struct node{
    int l;
    inline bool operator <(const node& x)const{
        return x.l > l;
    }
};
priority_queue <node> Q1;
priority_queue <node> Q2;
vector <int> ans_1;
vector <int> change;

int main() {
    n = read(), m = read(), q = read(), u = read(), v = read(), t = read();
    p = u * 1.0 / v;
    for(int i = 1; i <= n; i++) a[i] = read(), Q1.push((node){a[i]});
    for(int i = 1; i <= m; i++) {
        node top = Q1.top();Q1.pop();
        int x1 = (int)(top.l * p);
        int x2 = top.l - x1;
        Q1.push((node){x1}); Q1.push((node){x2});  
        if(i % t == 0) ans_1.push_back(top.l); 
    }
    int len = ans_1.size();
    for(int i = 0; i < len; i++) printf("%d ", ans_1[i]);
    putchar(10);
    int tot = 0;
    while(!Q1.empty()) {
        tot++;
        node top = Q1.top(); Q1.pop();
        if(tot % t == 0) {
            printf("%d ", top.l);
        }
    }
    return 0;
}

[70分做法]：

考试的时候想出来的一种做法。建立两个优先队列，结构体中增加c和b,用c表示该条蚯蚓上次被切割是在第c秒，b = l - c，然后以b的大小为关键字将所有的蚯蚓排列。先将所有蚯蚓存入Q1,每次切完后，将长的一条存入Q1,短的一条存入Q2,然后每次取出Q1和Q2队首中b的值更大的一条去切割。对于第i秒切割的蚯蚓，其当前长度则为\(l + (i-1) * q - c * q\), 而切割完后，每条蚯蚓当前长度则为\(l + (i - c) * q\)。

Code:

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
//Mystery_Sky
//->70
#define M 200010
#define INF 0x3f3f3f3f
#define ll long long
inline int read()
{
    int x=0,f=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}
int n, m, q, u, v, t;
double p;
int a[M];
struct node{
    int l;
    int c;
    int b;
    inline bool operator <(const node& x)const{
        return x.b > b;
    }
};
priority_queue <node> Q1;
priority_queue <node> Q2;
priority_queue <int> Q;
vector <int> ans_1;

int main() {
    n = read(), m = read(), q = read(), u = read(), v = read(), t = read();
    p = u * 1.0 / v;
    for(int i = 1; i <= n; i++) a[i] = read(), Q1.push((node){a[i], 0, a[i]});
    for(int i = 1; i <= m; i++) {
        node top_1;
        if(!Q1.empty()) top_1 = Q1.top(), Q1.pop();
        node top_2;
        top_2.l = -1;
        if(!Q2.empty()) top_2 = Q2.top(), Q2.pop();
        node top;
        if(top_2.l != -1 && top_1.b >= top_2.b) Q2.push(top_2), top = top_1;
        else if(top_2.l == -1) top = top_1;
        else Q1.push(top_1), top = top_2;
        int len = top.l - top.c + (i - 1) * q;
        int x1 = (int) (len * p);
        int x2 = len - x1;
        if(x1 < x2) swap(x1, x2);
        Q1.push((node){x1, i * q, x1-i*q});
        Q2.push((node){x2, i * q, x2-i*q});  
        if(i % t == 0) ans_1.push_back(len); 
    }
    int len = ans_1.size();
    for(int i = 0; i < len; i++) printf("%d ", ans_1[i]);
    putchar(10);
    while(!Q2.empty()) {
        node top = Q2.top(); Q2.pop();
        Q1.push(top); 
    }
    int tot = 0;
    while(!Q1.empty()) {
        tot++;
        node top = Q1.top(); Q1.pop();
        if(tot % t == 0) {
            printf("%d ", top.l - top.c + m * q);
        }
    }
    return 0;
}

(话说这样建两个优先队列似乎没有什么意义)

[正解]：

我们建立三个队列，嗯，就是普通的队列。先将所有的蚯蚓从大到小排序后放入Q[0]，然后每次切割后将其中一条放入Q[1],另外一条放入Q[2],由于切割时间的先后导致在同一个队列中先入队的蚯蚓长度总会大于后入队的，所以这三条队列本身就是单调的，每次切的时候取三个队列的队首中最大的一个切割即可。对于增长的长度q，暴力计算显然会t，我们可以增加变量add，表示已增长的长度，每次切割时先将蚯蚓长度加上add，切完后，将两段的长度减去（add + q），再入队，add加上q即可。

Code:

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
//Mystery_Sky
//
#define M 200010
#define INF 0x3f3f3f3f
inline int read()
{
    int x=0, f=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
queue <int> Q[3];
vector <int> ans_1;
int n, m, q, u, v, t, add;
double p;
int a[M];
inline bool cmp(int a, int b){return a > b;}
inline int big()
{
    int res = -1;
    for(int i = 0; i <= 2; i++) if(!Q[i].empty() && ((res == -1) || (Q[i].front() > Q[res].front()))) res = i;
    return res;
}

int main() {
    n = read(), m = read(), q = read(), u = read(), v = read(), t = read();
    p = u * 1.0 / v;
    for(int i = 1; i <= n; i++) a[i] = read();
    sort(a+1, a+n+1, cmp);
    for(int i = 1; i <= n; i++) Q[0].push(a[i]);
    for(int i = 1; i <= m; i++) {
        int top = big();
        int x = Q[top].front() + add; Q[top].pop();
        int x1 = (int)(x * p);
        int x2 = x - x1;
        x1 -= (add + q), x2 -= (add + q);
        Q[1].push(x1), Q[2].push(x2);
        if(i % t == 0) ans_1.push_back(x);
        add += q;   
    } 
    for(int i = 0, len = ans_1.size(); i < len; i++) printf("%d ", ans_1[i]);
    putchar(10);
    for(int i = 1; i <= n+m; i++) {
        int top = big();
        int x = Q[top].front(); Q[top].pop();
        if(i % t == 0) printf("%d ", x + add);
    }
    return 0;
}