icontofig | 发布于 2016-12-14 21:01:02 | 阅读量 302 | 机智题 单调队列
发布于 2016-12-14 21:01:02 | 机智题 单调队列

NOIP[2016Day2T2]蚯蚓

题目描述

本题中,我们将用符号[c]表示对c向下取整,例如:[3.0」= [3.1」=[3.9」=3。
蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有n只蚯蚓(n为正整数)。每只蚯蚓拥有长度,我们设第i只蚯蚓的长度为a_i(i=1,2,...,n),并保证所有的长度都是非负整数(即:可能存在长度为0的蚯蚓)。
每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数p(是满足0<p<1的有理数)决定,设这只蚯蚓长度为x,神刀手会将其切成两只长度分别为[px]和x-[px]的蚯蚓。特殊地,如果这两个数的其中一个等于0,则这个长度为0的蚯蚓也会被保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加q(是一个非负整常数)。
蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物,但是救兵还需要m秒才能到来...... (m为非负整数)
蛐蛐国王希望知道这m秒内的战况。具体来说,他希望知道:
m秒内,每一秒被切断的蚯蚓被切断前的长度(有m个数)
m秒后,所有蚯蚓的长度(有n+m个数)。
蛐蛐国王当然知道怎么做啦!但是他想考考你......

输入格式

第一行包含六个整数n,m,q,u,v,t,其中:n,m,q的意义见【问题描述】;u,v,t均为正整数;你需要自己计算p=u/v(保证0<u<v)t是输出参数,其含义将会在【输出格式】中解释。
第二行包含n个非负整数,为ai,a2,...,an,即初始时n只蚯蚓的长度。
同一行中相邻的两个数之间,恰好用一个空格隔开。
保证1<=n<=105 ,0<m<7*106 ,0<u<v<109 ,0<=q<=200 ,1<t<71 ,0<ai<108。

输出格式

第一行输出[m/t]个整数,按时间顺序,依次输出第t秒,第2t秒,第3t秒……被切断蚯蚓(在被切断前)的长度。
第二行输出[(n+m)/t]个整数,输出m秒后蚯蚓的长度;需要按从大到小的顺序,依次输出排名第t,第2t,第3t……的长度。
同一行中相邻的两个数之间,恰好用一个空格隔开。即使某一行没有任何数需要 输出,你也应输出一个空行。
请阅读样例来更好地理解这个格式。

样例输入

3 7 1 1 3 1
3 3 2

样例输出

3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2

样例输入2

3 7 1 1 3 2
3 3 2

样例输出2

4 4 5
6 5 4 3 2

样例输入3

3 7 1 1 3 9
3 3 2

样例输出3

2

限制与约定

保证每行输出的整数个数不超过 105
每个测试点的详细数据范围见下表。

题解

NOIP出这种丧心病狂的题也是真心坑爹啊……
只能说出题人太恐怖了
考场上无法想出此题解法,于是暴力跑了40分。现在想想还是挺后悔的,本来用STL水80分的题……
后悔联赛以前没有怎么做过单调队列的题,然后这种题只能听天由命
于是来看看这道题是怎么用单调队列来解的……
我们注意到,神刀手每次都是挑最长的一个蚯蚓x来切断它。对于某一时刻,有两个蚯蚓,长度分别为x和y且x>y。那么我们注意到,x切完后生成的两条蚯蚓,一定会比y切完后生成的两条蚯蚓都要长。
所以我们先将a数组从小到大排序,使其先形成一个单调队列。然后开两个单调队列(注意不要用STL,尽量手写),分别存储[p]x和[1-p]x,由上可以发现,神刀手每次完成操作,将新的两个蚯蚓推入队列后,后面的两个队列都是单调的,所以此题根本不需要单调队列的判断单调和出队操作。
后面的话,我们就每次取三个队头比较大小,取最大的切掉,并把新的两个蚯蚓分别推入后两个单调队列里面。如此循环m次,边操作边输出。然后此题就被我们做掉了
然后我在本校内部OJ(NOIP数据)上是满分,UOJ上的Extra Text表示力不能及,花式被卡,在BZOJ上又显示迷之的OLE(我得找找管理员了)然后大家可以参照下我的代码。
至于为什么用long double,我只能说,我在UOJ上被卡了一波精度,然后又被7号额外测试卡了TLE(迷……)。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxm = 7e6+5;
const int maxn = 1e5+5;
int s1,s2,s3,t1,t2,t3;
struct st{
    int x;
    int t;
};
bool cmp(st a,st b){
    return a.x > b.x;
}
st q1[maxm],q2[maxm],q3[maxm];
int a[maxn];
int n,m,q,t;
long double u,v;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num  = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
long double k,p;
int main(){
    freopen("earthworm.in","r",stdin);
    freopen("earthworm.out","w",stdout);
    n = get_num();
    m = get_num();
    q = get_num();
    cin >> u >> v;
    p = u/v;
    t = get_num();
    for(int i = 0;i < n;++i)
        scanf("%d",&q1[i].x),q1[i].t = 0;
    sort(q1,q1+n,cmp);
    s1 = s2 = s3 = 0;
    t1 = n;
    t2 = 0;
    t3 = 0;
    for(int i = 0;i < m;++i){
        long double o = 0;
        int pos = 0;
        if(t1 > s1){
            pos = 1;
            o = (long double)(q1[s1].x + (i - q1[s1].t)*q);
        }
        if(t2 > s2 && o < q2[s2].x + (i - q2[s2].t)*q){
            pos = 2;
            o = (long double)(q2[s2].x + (i - q2[s2].t)*q);
        }
        if(t3 > s3 && o < q3[s3].x + (i - q3[s3].t)*q){
            pos = 3;
            o = (long double)(q3[s3].x + (i - q3[s3].t)*q);
        }
        switch  (pos){
            case 1:s1++;break;
            case 2:s2++;break;
            default:s3++;break;
        }
        if((i+1) % t == 0)printf("%d ",(int)o);
        k = floor(o * p);
        q2[t2].x = (int)k;q2[t2].t = i+1;t2++;
        q3[t3].x = (int)(o - k);q3[t3].t = i+1;t3++;
    }
    printf("\n");
    int cnt = 0;
    while(t1 > s1 || t2 > s2 || t3 > s3){
        int o = 0;
        int pos = 0;
        if(t1 > s1 && o < q1[s1].x + (m - q1[s1].t) * q){
            pos = 1;
            o = q1[s1].x + (m - q1[s1].t) * q;
        }
        if(t2 > s2 && o < q2[s2].x + (m - q2[s2].t) * q){
            pos = 2;
            o = q2[s2].x + (m - q2[s2].t) * q;
        }
        if(t3 > s3 && o < q3[s3].x + (m - q3[s3].t) * q){
            pos = 3;
            o  = q3[s3].x + (m - q3[s3].t) * q;
        }
        switch (pos){
            case 1:s1++;break;
            case 2:s2++;break;
            default:s3++;break;
        }
        cnt++;
        if(cnt % t == 0)printf("%d ",o);
    }
    printf("\n");
    return 0;
}
​

内容更新于: 2016-12-14 21:01:01
链接地址: http://blog.leanote.com/post/icontofig/024d143efcff

上一篇: [NOIP2016day1T2]running天天爱跑步

下一篇: [NOIP2016Day1T3]换教室classroom

302 人读过
立即登录, 发表评论.
没有帐号? 立即注册
1 条评论
文档导航