http://codeforces.com/contest/1154/problem/E

解题:

举例n=10,k=1

1,2,10,4,7,6,9,8,5,3

第一次,1队先挑2,10,4这三个人

1,2,10,4,7,6,9,8,5,3

第二次,2队挑6,9,8三个人

1,2,10,4,7,6,9,8,5,3

第三次,1队挑1,7,5三个人

1,2,10,4,7,6,9,8,5,3

第四次,2队挑3一个人

1,2,10,4,7,6,9,8,5,

显然需要实现的有两点

(1)挑完后的“连接”,比如

第一次挑完后需要把1和7“连接”起来

第二次挑完后需要把7和5“连接”起来

用l数组标记当前下标 左边相邻的数的下标

用r数组标记当前下标 右边相邻的数的下标

例如一开始:

r[1]=2,表示下标为1的人(1)的右边是下标为2那个人(2)

l[5]=4,表示下标为5的人(7)的左边是下标为3那个人(4)

第一次挑完之后

r[1]=5,表示下标为1的人(1)的右边是下标为5那个人(7)

l[5]=1,表示下标为5的人(7)的左边是下标为1那个人(1)

每次挑完人后把已经挑选的人“删掉”,左右扩散找人可以通过左右数组来找人,直接跳过被挑选过的人,实现“删掉”,

(2)快速找最大值,暴力寻找肯定会超时

一般遇到n个不同的数随机出现在数组里,可以用下标数组idx标记这个数出现的下标位置,直接查找。

dix[10]=3表示10这个数在原数组的下标位置是3

这里可以从n开始减小,一直减到1,时间复杂度O(n)

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<vector>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#define inf 0x3f3f3f3f
#define ll long long
using namespace std; int n,k,maxxidx,maxx;
int a[];
int l[];///下标为i的人 的左边 下标是多少
int r[];///下标为i的人 的右边 下标是多少
int idx[];///标记原数组下标
int ans[]; void findmax()///找最大值,主要是改变全局变量maxxidx和maxx
{
while(maxx>=)
{
if( ans[ idx[maxx] ]== )
{
maxxidx=idx[ maxx ];
break;
}
maxx--;
}
} int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(a,,sizeof(a));
memset(l,,sizeof(l));
memset(r,,sizeof(r));
memset(idx,,sizeof(idx));
memset(ans,,sizeof(ans));
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
idx[ a[i] ]=i;
l[i]=i-;
r[i]=i+;
}
l[n+]=n;
r[]=;
maxxidx=idx[n];///初始化为最大的下标
maxx=n;
int now=;///当前已经选了多少人
int t=;///初始是1队先挑人
while(now<n)
{
findmax();
int i=maxxidx;///最大的那个人的下标
ans[i]=t;
now++;
int x=l[i];
int y=r[i];///中间向左右两边扩展
for(int j=;j<=k;j++)
{
if(x>= && x<=n)///如果x是0表明左边无人了
ans[x]=t,x=l[x],now++;///通过左右指针数组找下一个人
if(y>= && y<=n)
ans[y]=t,y=r[y],now++;
}
///挑完人就该改左右下标了
l[y]=x;
r[x]=y;
if(t==)
t=;
else
t=;
}
for(int i=;i<=n;i++)
printf("%d",ans[i]);
printf("\n");
}
return ;
}

最新文章

  1. 如何在CentOS/RHEL &amp; Fedora上安装MongoDB 3.2
  2. phpmyadmin连接,管理多个mysql服务器
  3. PHP乱码问题,UTF-8(乱码)
  4. springmvc里面的中文乱码问题
  5. 负载均衡集群之LVS的DR模型详解(Diretor Routing)
  6. linux日志(常用命令)
  7. Oracle SQL CPU占用高
  8. MPP 二、Greenplum数据加载
  9. JAVA基础-JDBC二(常用的开源工具)
  10. Design Mobile实现国际化
  11. spring的配置与使用
  12. maven 本地仓库无法更新到最新版本的jar包
  13. day 11 - 1 装饰器
  14. 关于使用python的open函数时报No Such File or DIr的错误
  15. chromedriver与google版本的对应
  16. Hadoop生态圈-注册并加载协处理器(coprocessor)的三种方式
  17. 学习C++的50条忠告
  18. java设计模式-----7、装饰模式
  19. LNMP环境修改上传文件大小
  20. python redis插件安装

热门文章

  1. failed to open stream: operation failed
  2. git 命令行回退到某个指定的版本
  3. 仿微信、qq聊天,@好友功能
  4. APUE之第5章——标准I/O库
  5. C#项目 App.config 配置文件不同使用环境配置
  6. MySQL5.6.17 绿色版 安装配置
  7. DevExpress之GridControl控件小知识
  8. 去世父亲在儿子手机中复活,这可能是最温暖的一个AI
  9. 量化金融策略开源框架:QUANTAXIS
  10. Java集合学习(8):LinkedList