首页 > 其他分享 >P4064 [JXOI2017] 加法 题解

P4064 [JXOI2017] 加法 题解

时间:2024-02-02 22:55:26浏览次数:27  
标签:JXOI2017 int 题解 mid 端点 P4064 include

P4064 [JXOI2017] 加法 题解

思路

一眼二分答案,这种区间的题很难不排序,可以考虑这个贪心 check:

区间左端点升序排序之后,每次遇到一个点,判断这个点是否合法,如果不合法就在所有左端点在这个点左边的区间里选择右端点最大的一个。

感性证明:这个点之前的点已经保证合法了,所有左端点在这个点左侧的区间左端点到这个点这部分只对当前点造成贡献,对后面无影响,所以显然选择右端点最大的可以让后面吃到最多的贡献。

然后就……做完了……

时间复杂度:\(O(n\log n\log V)\)。

// Problem: P4064 [JXOI2017] 加法
// Contest: Luogu
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-02-02 22:33:01

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define int long long
using namespace std;
const int N = 2e5 + 10;

int n, m, k, v, a[N];
pair<int, int> p[N];
priority_queue<pair<int, int> > heap;
vector<int> t[N];
struct BIT {
    int tr[N];
    void update(int i, int c)  { for (; i <= n + 1; i += i & -i) tr[i] += c; }
    void update(int i)  { for (; i <= n + 1; i += i & -i) tr[i] = 0; }
    int query(int i)  { int res = 0; for (; i; i &= i - 1) res += tr[i]; return res; }
    void clear() {memset(tr, 0, sizeof tr);}
} bit;

bool check(int mid) {
    while(heap.size()) heap.pop();
    for(int i = 1; i <= n; i ++) bit.update(i);
    int cnt = 0;
    for(int i = 1; i <= n; i ++) {
        for(auto j : t[i]) heap.push({p[j].second, j});
        while(cnt < k && bit.query(i) + a[i] < mid) {
            if(heap.empty()) return 0;
            int t = heap.top().second; heap.pop();
            bit.update(p[t].first, v), bit.update(p[t].second + 1, -v);
            cnt ++;
        }
        if(bit.query(i) + a[i] < mid) return 0;
    }
    return 1;
}
void work() {
    cin >> n >> m >> k >> v;
    for(int i = 1; i <= n; i ++) cin >> a[i], t[i].clear();
    for(int i = 1; i <= m; i ++) cin >> p[i].first >> p[i].second, t[p[i].first].push_back(i);
    int l = 1, r = 1e8, ans = 0;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(mid)) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    cout << ans << '\n';
    return ;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1; 
    cin >> T;
    while (T--) work();

    return 0;
}

标签:JXOI2017,int,题解,mid,端点,P4064,include
From: https://www.cnblogs.com/MoyouSayuki/p/18004164

相关文章

  • AT_past202107_l 题解
    Solution题目来源:AT_past202107_l(inAtCoder|inluogu)用线段树维护区间最小值。单点修改很好写,我们看怎么区间寻找最小值位置。对于每次询问,我们先求出所查询区间\([x_i,y_i]\)的最小值\(p\),然后写一个寻找函数。对于当前区间\([l,r]\),分以下情况来看:如果当前区间长......
  • CF1542E2 题解
    一、题目描述:设$\pi(x)$为全排列$x$的逆序对数。给定$n,m$,求有多少对长度为$n$ 的排列$p,q$,使得$p$的字典序小于$q$,且$\pi(p)>\pi(q)$答案对$m$取模。数据范围:$1\len\le500,1\lem\le10^9$。 二、解题思路:一开始列出计算式个人感觉是......
  • 230718B3-path 题解
    感谢cn_ryh大佬的怂恿(否则我真不会动这个题感谢cszhpdx的指导帮助qwq(让我们膜拜一下场切的浩杨哥orz解决这个题让人很有成就感(题意给定一个基环树,边有长度l、限速v、价值w(每单位时间)已知起点s、终点t、最高速度u,求最小花费边数、询问次数$10^5$解法首先学习一下基......
  • 基于客户真实使用场景的云剪辑Timeline问题解答与代码实操
    本文为阿里云智能媒体服务IMS「云端智能剪辑」实践指南第6期,从客户真实实践场景出发,分享一些Timeline小技巧(AI_TTS、主轨道、素材对齐),助力客户降低开发时间与成本。欧叔|作者故事的开始要从一条客户的真实反馈说起。  Round1:视频比音频长,怎么办?某天,一位客户加入了智能媒......
  • 盘点那些硬件+项目学习套件:Hi3861鸿蒙开发板及入门常见问题解答
    华清远见20岁了~过去3年里,华清远见研发中心针对个人开发板业务,打造了多款硬件+项目学习套件,涉及STM32单片机、嵌入式、物联网、人工智能、鸿蒙、ESP32、阿里云IoT等多技术方向。今天我们来盘点一下,比较受欢迎几款“硬件+项目”学习套件,以及一些初学者比较关注的问题。盘点二:Hi3861......
  • fatal: couldn't find remote ref master 问题解决!
    这个错误信息通常出现在使用Git命令尝试从远程仓库克隆、拉取(pull)或推送(push)时,指定的分支(在这个案例中是master)在远程仓库中不存在。这种情况可能由以下几个原因导致:1.分支名称错误远程仓库中不存在名为master的分支:随着Git和GitHub的更新,master分支被重新命名为main......
  • AcWing 520. 子串 题解
    ps:觉得这编号很特殊就做了一下题目传送门算法(线性DP,前缀和)\(O(nmk)\)首先考虑如何DP,然后再考虑如何优化。状态表示:f[i,j,k]表示只用S的前i个字母,选取了k段,可以匹配T的前j个字母的方案数。状态计算:将f[i,j,k]表示的所有方案分成两大类:不用S[i],则方案数是f[i-1,......
  • P9309 [EGOI2021] Number of Zeros题解
    模拟赛时以为是进位制的题目,结果还做出来了。此题解解法与其它相似,但观察的角度不同(作者的脑回路不同)。此题问\(a\simb\)的最小公倍数中后导\(0\)的个数,即求其中\(2\)和\(5\)个数的最小值。分别计算即可,想到进位制,以\(a=10\),\(b=12\)时\(2\)的个数为例:1001(9)......
  • P9612 [CERC2019] Light Emitting Hindenburg 题解
    题目传送门题目大意这个题目简化一下就是求\(n\)个数中取\(k\)个数按位与的最大值思路很容易想到贪心。题中说道输入的数在二进制下最多\(29\)位,所以我们从\(29\)开始遍历二进制位,如果当前位有大于等于\(k\)个\(1\),那么标记一下这些数,可以发现剩下的比当前位低的......
  • AcWing 3721. 求30的倍数 题解
    传送门stoi这里我们来了解一个函数\(stoi\)作用是将\(n\)进制的字符串转化为十进制,使用时包含头文件\(string\)定义如下:intstoi(conststd::string&str,std::size_t*pos=nullptr,intbase=10);参数:\(str\)-待转换的字符\(pos\)-其取值可以是一个空字......