CodeForces 1154E :Two Teams 思维_匿枫的博客-程序员秘密
传送门
题意
分析
很久以前比赛没写出来的一道题，翻出来补一下
我们维护两个优先队列 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;
}
智能推荐
Unity开发中刘海屏手机的屏幕适配_U3d_erer的博客-程序员秘密
Unity UGUI在刘海屏手机的屏幕适配主要是针对iPhoneX的适配。解决方法是每一个界面的最上层都是一个横纵Stretch自动拉伸的，当检测到当前是IPhoneX时，打开界面代码自动设置Left Top Right Bottom 为44.通过分辨率来判断当前手机是不是iPhoneX。 1 2 3 4 5 6 7 8...
数据并行和模型并行的区别_模型并行 数据并行 比较_FesianXu的博客-程序员秘密
此文翻译自[1]，[1]对数据并行和模型并行进行了很好地区分，因此这里推荐给大家。介绍现在深度学习模型的参数量已经变得越来越多了，数据集的尺寸也随之疯狂地增长。为了在一个巨大的数据集上训练一个复杂的深度学习模型，我们不得不使用多节点的并行方式，否则我们永远不可能达到这个目的。这里谈到的并行，通常指的有两种，或者它们各自的混合：数据并行 (Data Parallel)模型并行 (Mode...
android x264 编译库,AndroidFFmpegCompile_谢科-搜索引擎的博客-程序员秘密
做音视频开发，ffmpeg是绕不过去的开源库，我们要在Android 平台上运行ffmpeg，需要编译一个ffmpeg 动态库；1.编译环境ffmpeg源码：https://git.ffmpeg.org/ffmpeg.git下载下来之后切换到一个release分支，我切换的是n4.0.3分支；每个分支的情况编译都不一样，这个分支的代码尝试编译时可以的，推荐给大家吧；编译系统：Mac OS Xndk...
【Java环境搭建】搭建轻巧的Java编译运行环境【with sublime text 3 [已解决：加载主类问题 和 运行输出问题]】_sublime无法加载主类_青菜 - Teloy_041的博客-程序员秘密
搭建Java环境 [ with sublime text 3 ][by_041]【事先要先准备好sublime text 3噢~】下载安装Java：进入以下网址Java SE Downloads点击第一个看到的JDK Download链接(最新版是免费的，其他的都要登录账户才可下载)，进入相应版本Java的下载菜单下拉页面，找到合适版本的Java SE Development Kit下载安装在环境变量Path中添加所下载路径的/bin文件夹重启计算机验证：在cmd命令框中输入Java
element Popconfirm气泡确认框 confirm事件无效 解决方法_Tail96的博客-程序员秘密
confirm => onConfirmEvents事件名称 说明 回调参数onConfirm 点击确认按钮时触发 —cancel 点击取消按钮时触发 —
anaconda安装_AinUser的博客-程序员秘密
一般直接下一步下一步，在这里直接简述可能遇到问题的注意点1.安装anaconda，在这个步骤和python安装是有关系的，如果忘记了，这里可以记住当前选择项，文章末尾会验证此处是否正确 2.这里两个均需要勾选，主要是第一个，配置环境变量使用。3.这里直接点击跳过4.此处两个均不需要勾选，直接finish完成即可5.最后验证上述anaconda是否安装成功...
随便推点
J2EE学习笔记（一）_xiang_fu的博客-程序员秘密
J2EE模式 Value Object(值对象)用于把数据从某个对象/层传递到其他对象/层的任意Java对象。通常不包含任何业务方法。 也许设计有公共属性，或者提供可以获取属性值的get方法。JSP 1．JSP的基础知识 __ _____ | directive (指令) | |-- scripting（脚本） JS...
阿里云MaxCompute（ODPS）如何使用SQL同步数据（SQLTask模式）_王大雄_的博客-程序员秘密
odps指定sql下载：1.sqlTask号称不支持超过10000行，能否通过多次执行task、每次task限定分页条件实现获取全部数据；2.官方推荐的sqlTask+tableTunnel方案https://help.aliyun.com/document_detail/120601.html?spm=a2c4g.11186623.6.973.65b14317QHBhfLhttps://h...
麦克斯韦的故事_Mouse3D的博客-程序员秘密
一、生平简介 麦克斯韦(James Clerk Maxwel 1831～1879)英国物理学家，1831年6月13日生于英国爱丁堡的一个地主家庭，8岁时，母亲去世，在父亲的诱导下学习科学，16岁时进入爱丁堡大学，1850年转入剑桥大学研习数学，1854年以优异成绩毕业于该校三一学院数学系，并留校任职。1856年到阿伯丁的马里沙耳学院任自然哲学教授。1860年到伦敦任皇家学院自然哲学及天文学教
漏洞分析SQL Injection Attack Lab(自用,记录)_没有红茶也没有奶盖的博客-程序员秘密
SQL Injection Attack Lab1 Overview2 Lab Environment2.1 Environment Configuration2.2 Turn Off the Countermeasure2.3 Patch the Existing VM to Add the Web Application3 Lab Tasks3.1 Task 1: MySQL Console3.2 Task 2: SQL Injection Attack on SELECT Statement3.3 T
嵌入式linux面试题解析——Linux应用编程部分_qr_ljj的博客-程序员秘密
1、TCP与UDP的区别 TCP：是面向连接的流传输控制协议，具有高可靠性，确保传输数据的正确性，有验证重发机制，不会出现丢失或乱序。 UDP：是无连接的数据报服务，不对数据报进行检查与修改，无须等待对方的应答，会出现分组丢失、重复、乱序，但具有较好的实时性，UDP段结构比TCP的段结构简单，因此网络开销也小。 2、流量控制和拥塞控制 拥塞控制
namedmanager mysql_namedmanager搭建过程及配置_SEX专家的博客-程序员秘密
1 安装yum install httpd php-soap php-xml php-ldap php-common php-cli php-mysql php-intl php-process php-pdo php mysql-server mysql-devel mysql-libs mysql -yyum install bind-libs bind bind-sdb bind-devel...