题目链接: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 ;
}

最新文章

  1. 关于HTML面试题汇总之visibility
  2. 据说最近IMO中国队失利的一题
  3. GCD的其他方法
  4. mvc api
  5. PHP_解析xss攻击、sql注入
  6. C++11 多线程 教学(2)
  7. 网络数据(socket)传输总结
  8. 【机器学习笔记之一】深入浅出学习K-Means算法
  9. 使用storm分别进行计数和词频统计
  10. kubernets controller 和 CRD的扩展
  11. vivox23幻彩版手机怎么设置双击息屏
  12. Go 初体验 - 令人惊叹的语法 - defer.1 - 基本概念和用法
  13. python 获取前一天或前N天的日期
  14. java eclipse maven The superclass &quot;javax.servlet.http.HttpServlet&quot; was not found on the Java Build Path 解决方法
  15. 存储过程使用 in 添加多个参数的情况处理方式【转】
  16. 团队Git使用教程
  17. MFC对话框:模态对话框及其弹出过程
  18. SQLSERVER 函数大全
  19. 第一章 Linux内核简介
  20. Kubernetes学习之路(五)之Flannel网络二进制部署和测试

热门文章

  1. Arduino SPI驱动7引脚0.96寸OLED SSD1306 调试笔记
  2. xshell 与服务器断开连接后 服务停止500internal error
  3. skip connections
  4. Can't locate Math/Round.pm in @INC
  5. tomcat 下 base64图片上传超过2m的解决方案
  6. solr常见错误
  7. lombok的介绍、使用、简单分析和插件
  8. @Bean修饰的方法参数的注入方式
  9. 常见的Redis面试&quot;刁难&quot;问题,值得一读
  10. Scala中sortBy和Spark中sortBy区别