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

技术标签: 算法  大学ACM  

传送门

题意

在这里插入图片描述

分析

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

代码

#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;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/tlyzxc/article/details/121024537

智能推荐

陆奇万字演讲:世界新格局下的创业创新机会_只有技术上可行,需求真实存在,市场又能形成盈利-程序员宅基地

文章浏览阅读981次。文章仅供个人学习和转载记录使用,侵删。划重点:1、新冠疫情和国际环境正在极大地加速四大趋势第一是数字化的社会基础。第二是生命科学的前沿。第三是可持续的新能源。第四是全球经济发展和创新的重心从西方转移到亚洲。2、中国过去40年的成绩,本质上是“中国+开放市场”,下一阶段是“中国+技术”,这是巨大机会。3、在国际环境上,经济中心向亚洲转移是一个被加速了的历史趋势。创新中心转移,中国+技术所蕴含的机会,毫无疑问这是我们这个时代的机会。4、我们让AI进入每一条流水线、每一个厂房,将需要5年、1_只有技术上可行,需求真实存在,市场又能形成盈利

大华等其他NVR接入海康IPC H.264方法-程序员宅基地

文章浏览阅读1.4k次。有一次遇到这个问题,因为时间急,没有注意,这次一个朋友也遇到这个问题,各种百度,也没有看到答案只好自己研究了一下,最终发现以下方式来解决下面办法可以解决海康IPC不能能过ONVIF连接到大华等其他NVR,其实不是NVR的问题,是IPC默认设置的问题海康摄像机添加到大华NVR 目前大多数牌品摄像机基本可以与第三方NVR连接,前提编码格式采用H.264。通讯协议是 ONVIF协议..._大华录像机连接海康摄像头怎么设置编码

NR PUCCH UCI-程序员宅基地

文章浏览阅读2.3k次,点赞3次,收藏28次。NR PUCCH UCI 简介,翻译自ShareTechnote。_pucch uci

Hair卡通渲染的效果(各向异性)_78kavcom-程序员宅基地

文章浏览阅读4.6k次,点赞5次,收藏16次。Hair卡通渲染的效果-各向异性丽塔头发 各向异性渲染(截图)效果截图:最终渲染源码:丽塔头发 各向异性渲染(截图)各向异性的主要计算公式:Glossiness和Metallic: void AnisotropicSurface (Input IN, inout SurfaceOutputStandardAnisotropic o) { fixed4 c = tex2D ..._78kavcom

deepin安装kali工具最安全有效方法_deepin安装kali工具包-程序员宅基地

文章浏览阅读2.2w次,点赞2次,收藏19次。在deepin源中添加kali源的时候,很容易将系统搞崩溃,但是通过kali源去安装kali上面的工具又可能是最快最方便的,所以要安装kali工具最安全的方法就是在需要安装的添加Kali源,不需要的时候去除方法1在/etc/apt/目录下面先创建两个源,一个源包含kali源,另一个只有deepin源:kali:## Generated by deepin-installerdeb [b..._deepin安装kali工具包

Python自定义高精度小数计算来获取巴塞尔问题的近似值_1. 请写出求巴塞尔问题近似解的python代码-程序员宅基地

文章浏览阅读2.2k次,点赞3次,收藏5次。巴塞尔问题,也就是以下级数的和:∑n=1∞1n2=lim⁡x→∞(112+122⋯+1n2)\sum_{n=1}^{\infty}\frac{1}{n^2} =\lim_{x \to \infty} (\frac{1}{1^2}+\frac{1}{2^2}\cdots +\frac{1}{n^2} )n=1∑∞​n21​=x→∞lim​(121​+221​⋯+n21​)其精确值已经被证明是 π26\frac{\pi ^2}{6}6π2​现在用python编写程序从正面逼近巴塞尔问题的精确值直接计算_1. 请写出求巴塞尔问题近似解的python代码

随便推点

Windows Server 2016搭建DNS服务_winserver2016自建dns解析服务器-程序员宅基地

文章浏览阅读1.2k次。DNS解析实验环境:一台windows server 2019中文版,需要加域,服务端域hb.com,计算机全名为DC.hb.com,客户端域hb.com,计算机全名为SDC.hb.com服务端IP地址192.168.10.1/24,默认网关192.168.10.100,首选dns192.168.10.1关闭防火墙服务端配置服务端加完域之后,自动创建了一个自己主机的一个正向文件,反向文件还没有创建去创建一个反向文件右键,添加区域这里选择主要区域这里默认即可_winserver2016自建dns解析服务器

Android绘图Canvas笔记_android canvas画笔粗细-程序员宅基地

文章浏览阅读4.5k次,点赞3次,收藏7次。Canvas的翻译是画布,Android系统里面的的2D绘图用的就是它。对应Canvas,官方的解释是这样的: The Canvas class holds the “draw” calls. To draw something, you need 4 basic components: A Bitmap to hold the pixels, a Canvas to host the draw_android canvas画笔粗细

是时候把gitee仓库迁移回github了_github什么时候开始禁止迁移库-程序员宅基地

文章浏览阅读3.3w次,点赞19次,收藏63次。2019年年初的时候,github就宣布了为用户免费提供无限制的私有仓库服务,虽然每个仓库限制最多3个协同操作者,但这个消息仍然令人振奋。这就意味着,之前一直放在gitee(码云)上的项目可以迁移回github进行统一管理。那些叫什么study-xxx的学习类工程,还有一部分不开源的项目(你懂的)也可以安心放在github托管了。_github什么时候开始禁止迁移库

互动媒体技术之绘画系统_虚拟绘制原理-程序员宅基地

文章浏览阅读549次。一.绘画的概念百度百科上对于绘画的阐释为:绘画(painting)在技术层面上,是一个以表面作为支撑面,再在其之上加上颜色的做法,那些表面可以是纸张或油画布(canvas)、木材、玻璃、漆器或混凝土等。加颜色的工具可以通过画笔、也可以通过刷子、海绵或是布条等。在现代,还可以通过计算机软件用鼠标手写板进行数码绘图,实现无纸化数字图像保存,避免了资源的浪费。也使得观看照片更加方便、美观。在艺术用..._虚拟绘制原理

微信订阅号关联服务号,通过获取共同unionid,来获取用户信息(关联账号)_订阅号有unionid吗-程序员宅基地

文章浏览阅读3k次。openid:每个用户对每个公众号的OpenID是唯一的,对于不同公众号,同一用户的OpenID不同。unionId:同一个微信开放平台帐号下的移动应用、网站应用和公众帐号,用户的UinonID是唯一的。在开发小程序公众号时,有时需要打通用户信息。这时需要将应用放在同一账号下,来获取一个共同unionId实现过程:1.准备一个订阅号,一个服务号。(服务号用来提供授权)..._订阅号有unionid吗

算法——指数取模运算(蒙哥马利算法)-程序员宅基地

文章浏览阅读8.3k次,点赞11次,收藏38次。蒙哥马利算法简介蒙哥马利(Montgomery)幂模运算是快速计算a^b%k的一种算法,是RSA加密算法的核心之一。——百度百科用到的公式(a * b) % p = a % p * b % p % p推论base^exp % p = (base % p) * (base % p) * … *(base % p) % p(总共exp个小括号) 若为exp偶数 = (base^2 %...

推荐文章

热门文章

相关标签