The Preliminary Contest for ICPC Asia Xuzhou 2019 E. XKC's basketball team
2024-09-07 21:02:42
题目链接:https://nanti.jisuanke.com/t/41387
思路:我们需要从后往前维护一个递增的序列。
因为:我们要的是wi + m <= wj,j要取最大,即离i最远的那个j,每次索引一个wi都需要判断下是不是大于w(i+1),完成递增序列的维护。
代码里面能更好的理解为什么要维护一个递增的序列
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <map>
#include <cmath>
using namespace std; typedef long long LL;
#define inf 1e9
#define rep(i,j,k) for(int i = (j); i <= (k); ++i)
#define rep__(i,j,k) for(int i = (j); i < (k); ++i)
#define per(i,j,k) for(int i = (j); i >= (k); --i)
#define per__(i,j,k) for(int i = (j); i > (k); --i) const int N = (int)5e5 + ;
int arr[N];
int ans[N]; struct node{
int index;
int w; void set(int x,int y){
index = x;
w = y;
}
}que[N]; int main(){ int n,m;
scanf("%d%d",&n,&m);
rep(i,,n) scanf("%d",arr+i); int l,r,mid,A;
int len = ;
//最后一个先处理
que[++len].set(n,arr[n]);
ans[n] = -;
//
per(i,n-,){ //比之前的都大
if(arr[i] + m > que[len].w){
ans[i] = -;
if(arr[i] > que[len].w)
que[++len].set(i,arr[i]);
}
//比第一个还小
else if(arr[i] + m <= que[].w){
ans[i] = que[].index - i -;
// printf("this is %d test ans is %d \n",i,ans[i]);
}
//在中间有答案
else{
l = ;
r = len;
while(l <= r){
mid = (l + r) >> ;
if(arr[i] + m <= que[mid].w){
A = que[mid].index;
r = mid - ;
}
else l = mid + ;
}
// printf("arr[%d] = index %d - index %d - 1\n",i,A,i);
ans[i] = A - i -;
}
} // rep(i,1,ll) printf("%d ",que[i].index);
// printf("\n"); printf("%d",ans[]);
rep(i,,n) printf(" %d",ans[i]);
printf("\n"); getchar(); getchar();
return ;
}
最新文章
- 关于HTML面试题汇总之visibility
- 据说最近IMO中国队失利的一题
- GCD的其他方法
- mvc api
- PHP_解析xss攻击、sql注入
- C++11 多线程 教学(2)
- 网络数据(socket)传输总结
- 【机器学习笔记之一】深入浅出学习K-Means算法
- 使用storm分别进行计数和词频统计
- kubernets controller 和 CRD的扩展
- vivox23幻彩版手机怎么设置双击息屏
- Go 初体验 - 令人惊叹的语法 - defer.1 - 基本概念和用法
- python 获取前一天或前N天的日期
- java eclipse maven The superclass ";javax.servlet.http.HttpServlet"; was not found on the Java Build Path 解决方法
- 存储过程使用 in 添加多个参数的情况处理方式【转】
- 团队Git使用教程
- MFC对话框:模态对话框及其弹出过程
- SQLSERVER 函数大全
- 第一章 Linux内核简介
- Kubernetes学习之路(五)之Flannel网络二进制部署和测试
热门文章
- Arduino SPI驱动7引脚0.96寸OLED SSD1306 调试笔记
- xshell 与服务器断开连接后 服务停止500internal error
- skip connections
- Can't locate Math/Round.pm in @INC
- tomcat 下 base64图片上传超过2m的解决方案
- solr常见错误
- lombok的介绍、使用、简单分析和插件
- @Bean修饰的方法参数的注入方式
- 常见的Redis面试";刁难";问题,值得一读
- Scala中sortBy和Spark中sortBy区别