CodeForces 1154E :Two Teams 思维-程序员宅基地

题意

在这里插入图片描述

分析

很久以前比赛没写出来的一道题，翻出来补一下
我们维护两个优先队列 $q, p$ ，把所有人的信息丢到队列 $q$ 中，同时维护前驱和后继，每次取出最大的那个，然后遍历他的前驱和后继的 $k$ 个节点，把信息丢到队列 $p$ 中，这样，只要 $p, q$ 两个队列的 $t o p$ 信息相同，就说明已经被找过了，应该 $p o p$ 掉

代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define dl(x) printf("%lld\n",x);
#define di(x) printf("%d\n",x);
#define _CRT_SECURE_NO_WARNINGS
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
const ll mod = 1000000007;
const double eps = 1e-9;
const double PI = acos(-1);
template<typename T>inline void read(T &a) {
    
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {
    if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}
int gcd(int a, int b) {
    return (b > 0) ? gcd(b, a % b) : a;}
priority_queue<PII>q,p;
int a[N],pr[N],ne[N];
int st[N];
int n,k;

int main() {
    
    read(n),read(k);
    for(int i = 1;i <= n;i++){
    
        read(a[i]);
        pr[i] = i - 1;
        ne[i] = i + 1;
        q.push({
    a[i],i});
    }
    ne[n] = 0;
    int flag = 0;
    while(q.size()){
    
        while(p.size() && q.top() == p.top()) q.pop(),p.pop();
        if(!q.size()) break;
        int i,j,t;
        for(i = 0,j = ne[q.top().se];i < k && j;i++,j = ne[j]) {
    
        	st[j] = flag,p.push({
    a[j],j});
        }
        for(i = 0,t = pr[q.top().se];i < k && t;i++,t = pr[t]) {
    
        	st[t] = flag,p.push({
    a[t],t});
        }
        st[q.top().se] = flag;
        pr[j] = t,ne[t] = j;
        st[q.top().se] = flag;
        q.pop();
        flag ^= 1;
    }
    for(int i = 1;i <= n;i++) printf("%d",st[i] + 1);
    return 0;
}

本文链接：https://blog.csdn.net/tlyzxc/article/details/121024537

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

文章浏览阅读3.2w次，点赞22次，收藏170次。主要软件1.UnityStudio 用于破解资源2.DNSPY 用于反编译代码并进行修改3.ILSPY 同上，差不多功能资源部份下面拿steam游戏《传说法师》作为例子进行解包。游戏资源可以使用UnityStudio软件获取。如果是安卓包可以将后缀改为.zip解压出文件夹。首先选择File->Load folder->游戏目录然后我们就可以预览资源了，并且可以导出想要的资源。代码部分这里使用的DNSPY软件。首先用软件打开游戏目录下Managed文件夹下的Assembl_unity游戏解包

AD20规则检查_ad pcb规则检查结果在哪看-程序员宅基地

文章浏览阅读1.4k次。AD20原理图规则检查首先进入工程-工程选项我这是按照默认选项。编译原理图这里就和网上大多数不一样了，后来有一篇博主说的是版本问题。出错！！！我本以为直接编译之后相关信息就会弹窗跳出，结果风平浪静，啥啥都没有，后来发现要点击右下角的panels选项，再选择message选项，就能看到DRC检查结果了。..._ad pcb规则检查结果在哪看

【Linux】获取Linux指令结果的指定列、指定行_linux如何取第几列-程序员宅基地

文章浏览阅读9.1k次，点赞8次，收藏32次。【代码】【Linux】获取Linux指令结果的指定列、指定行。_linux如何取第几列

基于最大似然估计(matlab实验)_matlab最大似然法-程序员宅基地

文章浏览阅读4.8k次，点赞8次，收藏26次。在逻辑分类的代价函数的推导过程中使用了最大似然估计，但最大似然估计求的是最大值，而代价函数求得是最小值，因此只差一个负号，这里的代价函数其实是一个交叉熵。除了梯度下降算法，还可以使用BFGC(变换度法)、L-BFGS(限制变尺度法)，这些算法的优点是可以自动选取好得学习率，通常比下降算法要快的多，但也比较复杂。2、针对二分类问题，采用matlab编程，得到分类结果，实验通过程序，分析，加深对逻辑回归分类问题的理解。第一、二列是入学前考试的成绩，第三列为是否可以入学：1(可以)，2(不可以)_matlab最大似然法

openstack 好文-程序员宅基地

文章浏览阅读459次。别以为真懂Openstack: 虚拟机创建的50个步骤和100个知识点 2016年08月14日 20:33:47 peach_li 阅读数：12256 转载自..._api neutron access control

Untiy中Camera上的Audio Listener组件的作用以及注意事项-程序员宅基地

文章浏览阅读6.4k次，点赞3次，收藏11次。Audio Listener组件的作用以及注意事项AudioListenerAudioListener 是游戏中的声音接收器，一般位于 Main Camera 游戏对象上，它可以接收游戏中的所有音乐和音效（只要其所附加的游戏物体在音效的影响范围内），此外，每一个 Scene 中仅有一个 Audio Listener。挂载方式：1.Audio Listener组件是可以挂载在相机或者其他位..._audio listener

随便推点

【python】将自定义常用的一些函数封装成可以直接调用的模块方法_python 函数封装为方法本地调用-程序员宅基地

文章浏览阅读1.7w次，点赞67次，收藏421次。将常用一些的函数封装成可以直接调用的模块方法1. 背景2. 具体步骤3. 扩展1. 背景在实际的操作过程中，经常会用到一个功能，如果每次编写代码的时候都进行重新编写或者打开已经编写好的函数进行复制粘贴，这样就显得很麻烦，有没有什么方法可以像导入python模块的那样，直接把要用的函数以模块名+方法的形式调用呢？答案当然是可以的，比如做数据分析时候经常要使用的功能是：实现某一路径下的所有xlsx的合并，文件如下直接给出合并的函数，保留数据格式筛选的接口，将合并后的数据保存在fltered_data文_python 函数封装为方法本地调用

CORE-ESP32C3|eink|墨水屏日历|天气API|LuatOS公共接口|气象要素数据V1|collectgarbage|LuatOS-SOC接口|官方demo|学习（13）：墨水屏动态日历_air105驱动墨水屏幕-程序员宅基地

【matlab非线性规划工具箱安装2 GloptiPoly 3.10工具箱】-程序员宅基地

文章浏览阅读910次，点赞13次，收藏23次。GloptiPoly 3是一个用于多项式优化的MATLAB工具箱，主要用于解决多项式优化问题。GloptiPoly 3由Didier Henrion、Jean-Bernard Lasserre和Mohab Safey El Din等人开发，是GloptiPoly工具箱的升级版本，旨在提供更强大和高效的多项式优化功能。它构建在先前版本的基础上，并引入了新的算法和功能。应用：GloptiPoly 3主要用于解决多项式优化问题，这些问题在控制理论、信号处理、机器学习、机器人学等领域中具有重要的应用。

miui系统备份恢复失败（一招解决，，无需技术也行）_miui备份文件bak恢复app-程序员宅基地

文章浏览阅读8.4k次，点赞2次，收藏3次。刷机，刷第三方rec,线刷，root等各个原因手机数据被清空，想把备份文件或apk的数据恢复的时候发现恢复失败，让人很头疼。原因:可能恢复过程中descript.xml文件出了点问题!!!准备软件:mt管理器这种问题别慌，先去应用商店下载恢复失败的呢个软件，如果应用商店没有的app,也有办法把软件恢复过来。应用商店没有的点击这里点这里跳转1.下载安装玩想恢复数据的软件以后，打开手机的备份。选择一个文件并备份。2.然后打开:/MIUI/Bckup/AllBackup的文件夹，然后把旧的后缀_miui备份文件bak恢复app

mysql表结构导出word_利用word宏功能一键导出数据库表结构-程序员宅基地

文章浏览阅读638次。前言：需求是：为了完成《数据库设计文档》中的表结构展示，需要导出所有的表结构，包括字段名、长度、注释等必要标题。数据库：MySQL我选择的方法是——用word的宏功能导出。很多博客已经记录过这个功能了，但每个人在过程遇到的问题可能都不一样，我也是花了大半天时间才解决。于是写这篇文章作为学习笔记，同时希望帮助到有同样需求的朋友。进入正题：第一步：查看自己的word有没有宏功能查看步骤：看到word..._word导出mysql表结构

docker run -d 一启动就退出的解决方法分享_docker run -d centos 自动退出-程序员宅基地

文章浏览阅读3.5k次，点赞2次，收藏7次。docker run -d启动失败的处理方法分享_docker run -d centos 自动退出