首页 > 其他分享 >洛谷题单指南-二叉堆与树状数组-P2827 [NOIP2016 提高组] 蚯蚓

洛谷题单指南-二叉堆与树状数组-P2827 [NOIP2016 提高组] 蚯蚓

时间:2024-11-08 09:31:18浏览次数:1  
标签:NOIP2016 maxx int 洛谷题 P2827 每次 数都 que 复杂度

原题链接: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

相关文章

  • 洛谷题单指南-二叉堆与树状数组-P1801 黑匣子
    原题链接:https://www.luogu.com.cn/problem/P1801题意解读:动态维护一组序列,并随时可以求第k小的值,每次求第k小的顺序是递增的,比如第一次取第1小,然后是第2小,以此类推。解题思路:对于求第k小的问题,已经介绍过几种方案:1、快选算法,每次查询时间复杂度logn,传送门:https://www.cnblogs......
  • 洛谷题单指南-二叉堆与树状数组-P3378 【模板】堆
    原题链接:https://www.luogu.com.cn/problem/P3378题意解读:实现二叉堆。解题思路:二叉堆本质上一棵完全二叉树,根节点称为堆顶,根据特性不同分为有两种:大根堆:所有父节点的值大于子节点,根节点最大小根堆:所有父节点的值小于子节点,根节点最小主要作用:动态维护序列,并快速找到最大/最......
  • 洛谷题单指南-字符串-P6824 「EZEC-4」可乐
    原题链接:https://www.luogu.com.cn/problem/P6824题意解读:已知整数序列a[i],i在1~n,有整数k,求一个整数x,要求a[i]^x<=k,使得符合要求的a[i]数量最多,求这个数量。解题思路:1、确定x的范围由于a[i]^x<=k,因此,x的有效二进制位不可能超过a[i],而a的取值范围<=1000000,因此x差不多......
  • 洛谷题单指南-字符串-P3369 【模板】普通平衡树
    原题链接:https://www.luogu.com.cn/problem/P3369题意解读:平衡树的基本操作,模版题。解题思路:1、二叉搜索树-BST二叉搜索树满足这样的性质:每一个节点的权值大于它的左儿子,小于它的右儿子。对BST进行中序遍历,将得到一个从小到大的有序序列,因此BST是为了维护一个有序序列的动态......
  • 洛谷题单指南-字符串-P4735 最大异或和
    原题链接:https://www.luogu.com.cn/problem/P4735题意解读:已知长度为n的数组a[],要在l~r范围找到一个p,使得a[p]^a[p+1]^...^a[n]^x最大,求这个最大的异或值。解题思路:1、利用前缀和将问题转化设s[]是a[]的前缀异或数组,要计算a中一段范围l~r的异或,可以借助于s由于s[r]=a[0]^a[......
  • 洛谷题单指南-字符串-P2922 [USACO08DEC] Secret Message G
    原题链接:https://www.luogu.com.cn/problem/P2922题意解读:已知M个01串,给出N个01串,对于N个串的每一个,求在M个串中有多少与其有公共前缀,且前缀长度是两个串中较小者。解题思路:用Trie树存储M个01串,用cnt1[]记录某个节点结束的01串个数,cnt2[]记录经过某个节点的01串的数量对于N个0......
  • 洛谷题单指南-字符串-P2375 [NOI2014] 动物园
    原题链接:https://www.luogu.com.cn/problem/P2375题意解读:计算字符串所有子串的不重叠相同前后缀数量。解题思路:1、KMP+暴力通过Next数组,可以计算所有子串相同前后缀的数量然后枚举Next数组,通过回跳Next[j]、Next[Next[j]-1]、Next[Next[Next[j]-1]-1]......来统计长度小于......
  • 洛谷题单指南-字符串-P3435 [POI2006] OKR-Periods of Words
    原题链接:https://www.luogu.com.cn/problem/P3435题意解读:定义字符串a是b的周期,当a是b的真前缀,且b是aa的前缀。给定字符串s,求s每一个前缀的最大周期长度之和。解题思路:针对字符串babababa进行样例模拟:前缀子串  最大周期  周期长度b空0ba空0babba2......
  • 洛谷题单指南-字符串-Test
    原题链接:https://www.luogu.com.cn/problem/CF25E https://codeforces.com/contest/25/problem/E题意解读:给定a,b,c三个字符串,求包含a、b、c的最短字符串长度。解题思路:要得到包含a、b、c的字符串,可以通过a、b、c连接形成,而要使得连接后的字符串最短,可以尽可能的利用重叠部分......
  • 洛谷题单指南-字符串-P1470 [USACO2.3] 最长前缀 Longest Prefix
    原题链接:https://www.luogu.com.cn/problem/P1470题意解读:求s最长前缀长度,使得可以拆解成p集合中的字符串解题思路:动态规划:设s字符串下标从1开始,p集合用set<string>保存所有的元素状态表示:设f[i]表示前i个字符s[0~i-1]是否能拆解成p中的元素状态计算:对于j=i-1开始往后倒......