CSU-1170 A Simple Problem
2024-09-04 04:11:51
题目链接
http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=1170
题目
Description
在一个由N个整数组成的数列中,最多能找到多少个位置连续的整数且其中的最大值与最小值之差不超过K呢?
Input
输入包含若干组数据。每组数据的第一行有2个正整数,N(1<=N<=\(10^6\)), K(0<=K<=\(10^6\)),其中N、K的含义同上,接下来一行一共有N个32位有符号整数(32-bit signed integer),依次描绘了这个数列中各个整数的值。
Output
对于每组数据,输出一个正整数,表示在这个数列中最多能找到多少个位置连续的整数且其中的最大值与最小值之差不超过K。
Sample Input
4 2
3 1 5 2
3 2
3 1 2
Sample Output
2
3
Hint
由于数据量较大,建议C++选手选用scanf来读取数据。
题解
因为题目要求连续的位置,那么我们直接扫一遍即可,初始\(l=1,r=1\),期间用multiset维护当前序列有多少个数,每次先判断一下multiset里最大数和最小数的差是否大于k,大于的话则则弹出\(a[l]\),不大于的话则加入\(a[r]\),顺便统计一下答案的最大值即可
AC代码
#include<bits/stdc++.h>
#include<set>
#define ll long long
#define maxn 1000050
using namespace std;
ll a[maxn];
inline ll getnum() {
char c; ll ans = 0; ll flag = 1;
while (!isdigit(c = getchar()) && c != '-');
if (c == '-') flag = -1; else ans = c - '0';
while (isdigit(c = getchar())) ans = ans * 10 + c - '0';
return ans * flag;
}
int main() {
ll n, k;
multiset<ll> s;
while (scanf("%lld%lld", &n, &k) != EOF) {
s.clear();
for (int i = 1; i <= n; i++) {
a[i] = getnum();
}
int l = 1, r = 1;
int ans = 0;
s.insert(a[r]);
while (r <= n) {
ll now = *(--s.end()) - *(s.begin());
if (now > k) {
multiset<ll>::iterator it;
it = s.find(a[l]); l++;
s.erase(it);
}
else {
ans = max(r - l + 1, ans);
if (r + 1 <= n) s.insert(a[++r]);
else break;
}
}
printf("%d\n", ans);
}
return 0;
}
/**********************************************************************
Problem: 1170
User: Artoriax
Language: C++
Result: AC
Time:752 ms
Memory:56700 kb
**********************************************************************/
最新文章
- 微信禁用右上角的分享按钮,WeixinJSBridge API以及隐藏分享的子按钮等菜单项
- nyoj-一笔画问题-欧拉图+联通判定
- arguments.callee的用法
- Scalaz(14)- Monad:函数组合-Kleisli to Reader
- No Dialect mapping for JDBC type: -9
- JS 中的五个假值
- 部署WEB应用程序
- 如何找出MySQL数据库中的低效SQL语句
- Python 基础篇:数据类型、数据运算、表达
- 老漏洞easy击:CVE-2012 0158占顶!
- C++常变量
- React修改state(非redux)中数组和对象里边的某一个属性的值
- Spring MVC 使用介绍(六)—— 注解式控制器(二):请求映射与参数绑定
- Javascript入门(一)弹出方框
- 7th,Python基础4——迭代器、生成器、装饰器、Json&;pickle数据序列化、软件目录结构规范
- git aliases
- MySql 8小时解决方案:proxool连接池
- 搭建一个基于CentOS的可视化zookeeper管理工具zkUI实现对zk的可视化管理
- 初拾Java(问题一:404错误,页面找不到)
- 最新zencart支付宝插件(支持1.5)