【尺取法】【Multiset】bzoj1342 [Baltic2007]Sound静音问题
2024-09-02 14:52:49
O(n)地枚举所有长度为k的段,每次暴力转移。
转移的时候只是从最后插入一个数,从前面删去一个数。
计算的时候要取当前的max和min。
用multiset(∵元素是可重的)以上这些操作都是O(logn)的。
#include<cstdio>
#include<set>
using namespace std;
multiset<int>S;
multiset<int>::iterator it;
int n,m,limit; bool goal;
int a[];
int main()
{
scanf("%d%d%d",&n,&m,&limit);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=m;i++) S.insert(a[i]);
it=S.end(); it--;
if((*it)-(*S.begin())<=limit) puts(""),goal=;
for(int i=;i<=n-m+;i++)
{
S.erase(S.find(a[i-]));
S.insert(a[m+i-]);
it=S.end(); it--;
if((*it)-(*S.begin())<=limit) printf("%d\n",i),goal=;
}
if(!goal) puts("NONE");
return ;
}
最新文章
- 微信支付开发(1) 微信支付URL配置
- Django Models的数据类型
- sql for xml 嵌套
- JDK5-可变参数
- javascript判断键盘按键
- (IOS)多线程开发
- (sqlite3.OperationalError) no such table: users [SQL: &#39;SELECT users.id AS users_id, users.email AS users_email, users.username AS users_username, users.role_id AS users_role_id, users.password_hash A
- Nancy启用跨站攻击防护(CSRF)
- [ExtJS5学习笔记]第二十三节 Extjs5中表格gridpanel的列格式设置
- 关于redis服务无法启动问题
- Find K Closest Elements
- debian系linux墙内安装安全工具集
- 一、Composer下载安装
- 象棋start
- makefile解析:一些常用函数
- hdu-2227-dp+bit
- Java动态代理学习
- Flash数据的采集方法-搜房房价走势采集
- Leetcode 429. N-ary Tree Level Order Traversal
- Java的IO流各个类的使用原则