蓝桥杯--快排+队列+尺取法
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
😃一起玩吧这世界那么多人（电影《我要我们在一起》主题曲 - 莫文蔚 - 单曲 - 网易云音乐
前言
这是我在CSDN做算法技能树遇到的第一个卡点接着又在POJ找了道类似题目,挺综合的
刚好学了快排队列尺取法(也叫双指针,是一种算法思想,用的原理就是队列),就练练手呗
杰西卡是日志统计的进阶版本
日志统计
题目1地址：(代码选择题,数据量达10^5)
题目
如果填空题 --> 代码题,我们该怎么做呢
思路
1,
注意!! 时间D的区间[T, T + D),是左闭右开的,所以代码第25行是 >= d
2,
结构体联系时刻ts和编号id
flag数组记录热帖
num数组记录某个帖子时间D内赞的数量
3,
核心代码是第23~30行,已知排序后时间ts从小到大
第23行:遍历
第24行:编号为a[i].id的帖子获赞数+1
第25行:若右边界时间 - 左边界时间 >= d(i"指针"走在前,j"指针"走在后)
第26行:取消左边界帖子获赞
第27行:左边界右移(有队列出队那味了)
第29行:若时间 [i - d, i) 上帖子 a[i].id 获赞数达k
第30行:flag数组标记热帖
代码
#include<iostream>
#include<cstdio> //scanf()
#include<algorithm> //sort()
using namespace std;
const int N = 100010;
int flag[N], num[N]; //记录热帖和获赞数
struct good
{
int ts, id;
};
bool cmp(good x, good y)
{
return x.ts < y.ts; //时间从小到大排序
}
int main()
{
struct good a[N];
int n, d, k; //数量时间获赞
scanf("%d%d%d", &n, &d, &k);
for(int i = 0; i < n; ++i)
scanf("%d%d", &a[i].ts, &a[i].id);
sort(a, a + n, cmp);
for(int i = 0, j = 0; i < n; ++i) {
num[a[i].id]++;
if(a[i].ts - a[j].ts >= d) {
num[a[j].id]--; //取消左边界的获赞
j++; //左边界右移
}
if(num[a[i].id] >= k) //时间[i-d, i)上达k个赞
flag[a[i].id] = 1;
}
for(int i = 0; i < n; ++i)
if(flag[i] == 1) //注意这里是i不是a[i].id
printf("%d\n", i);
return 0;
}
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
1
3杰西卡的阅读问题
不容易,POJ上百万用户,只有4700人做过这道题
还-有-700-人-做-不-出-来
一点一点看ACM大佬们0注释的代码(地图,哈希,二分,双队列,STL库,动不动一两百行)有些语法让人一头雾水
所幸思路有了,就可以找自己会的代替办法
POJ和ACM一样,就算Accpted 90%也是WA
第一次测试数据过了, 没用cin, 也没用STL库(sort(), min()),WA!!!!!!!!!!!!
第二次,找了半小时,在讨论区找了6组数据,解决了个小bug,Runtime Error!!!!!!!!!!!!!!!!!!!!!!!!
第三次,CSDN提问题解决了,感谢CSDN
最终AC😀
讨论区说不要用STL库的内容,比如min(), sort(),用了就过不了,必须自己写
题目2地址：（浏览器可翻译(数据量++,达10^6)
3320 -- Jessica's Reading Problem (poj.org)
题目
杰西卡必须掌握一本非常厚的教科书中包含的所有想法,该教科书有些想法不止一次被涵盖
杰西卡认为如果她设法至少阅读一次每个想法她就可以通过考试
她决定只阅读本书的一个连续部分其中包含整本书涵盖的所有思想
当然子书应该尽可能薄
每个想法都使用一个 ID 进行编码该 ID 是一个非负整数
输入
输入的第一行是整数P（1≤P≤1000000这是杰西卡教科书的页数。第二行包含 P 个非负整数描述每个页面的想法。第一个整数是第一页的内容第二个整数是第二页的内容依此类推
假设出现的所有整数都可以很好地适应有符号的 32 位整数类型(这就是代码1数组b越界的原因!!)
输出
输出一行：包含所有书中所有想法的最短连续部分的页数
输入例子
5 1 8 8 8 1
输出例子
2
也就是求,所有数字都包括在队列中的最小连续页数,或者说最短区间
考察
1队列
2快排
3scanf()比cin快
4尺取法
5如何判断尺取法所取的片段,包括了所有元素?
关于队列：
《啊哈算法》第二章栈队列链表（解析+代码_码龄11天的博客-CSDN博客
队首删除一个数的操作是：head++;
队尾增加一个数的操作是：q[tail] = x; tail++;
关于快排：
C++快速排序之整型数组_码龄11天的博客-CSDN博客_c++整数排序
让我再手写一次快排
void quick_sort(int left, int right, int a[])
{
if(left >= right) return;
int i, j, base;
i = left, j = right, base = a[left];
while(i < j) {
while(i < j && a[j] >= base) j--;
while(i < j && a[i] <= base) i++;
if(i < j) {
a[i] = a[i]^a[j];
a[j] = a[i]^a[j];
a[i] = a[i]^a[j]; //异或交换两数
}
}
a[left] = a[j]; //左端与i,j指向元素交换
a[j] = base;
quick_sort(left, j - 1, a); //递归左边
quick_sort(j + 1, right, a); //递归右边
}
关于scanf()：
cin关闭流同步的利弊与cout的endl使用_光風霽月的博客-CSDN博客_为什么不关cin
关于尺取法：
尺取法是算法竞赛中,常用的优化技巧
尺取法（图文解析、初学推荐_小白小郑的博客-CSDN博客_尺取法
(2条消息) 算法基础----尺取法（双指针_jkaliang的博客-CSDN博客
尺取法比暴力枚举区间的效率高很多（特别是数据量大时比如10^6是一种高效枚举区间的方法用于求取有一定限制的区间个数或最短区间
本题中通过左边界右移,右边界右移的方法,找到满足区间,并用ans(wer)保留最小区间
5,关于如何判断尺取法的区间包含了所有元素
我们用数组b保存a中不重复元素,得到不重复元素个数num
遍历时,设置游标 i ,游标右移过程中,代表区间的结束位置
得到num后,数组b使命结束,初始化数组b
每到达一页 i ,如果该页内容 a[i] 原来不在区间内,即b[a[i]] == 0
令b[a[i]]++, 表示区间内a[i]的个数为b[a[i]]个, 然后cnt++(cnt是count的意思)
-- --后面出队和包含所有数判断的操作,与第一题一样,不再赘述-- --
代码1
这是我Runtime Error的代码
#include<iostream>
#include<cstdio> //scanf(), printf()
#include<cstring> //memset()
const int N = 1000100;
int a[N], b[N];
int main()
{
int n, num = 0, cnt = 0;
scanf("%d", &n);
int ans = n;
for(int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
if(b[a[i]] == 0) {
num++;
b[a[i]] = 1;
} //得到不重复元素个数num
}
memset(b, 0, sizeof(b)); //初始化数组b
for(int i = 0, j = 0; i < n; ++i) {
if(b[a[i]] == 0) //a[i]原来不在区间内
cnt += 1; //区间内不重复元素个数
b[a[i]]++; //区间内a[i]个数
while(cnt == num) { //区间包括所有内容,这里不用if
if(ans > i - j + 1) ans = i - j + 1;
b[a[j]]--;
if(b[a[j]] == 0) cnt--;
j++; //左边界右移, j++记得放最后
}
}
printf("%d", ans);
return 0;
}
Runtime Error一般表示数组越界,由题目可知,每个数字最大为32位整型,这时让数组b一一对应就会越界,比如
2
0 173741824这是大佬用了map后AC的代码👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇👇
关于map C++硬货——map头文件【保姆级教学】_白凤倚剑归的博客-CSDN博客
代码2
#include<cstdio> //scanf(), printf()
#include<map>
int a[1000100];
std::map<int, int> b;
std::map<int, int>::iterator it;
int main()
{
int n, num = 0, cnt = 0;
scanf("%d", &n);
int ans = n;
for(int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
if(b[a[i]] == 0) {
num++;
b[a[i]] = 1;
} //得到不重复元素个数num
}
for(it = b.begin(); it != b.end(); it++)
it->second = 0; //初始化b
for(int i = 0, j = 0; i < n; ++i) {
if(b[a[i]] == 0) //a[i]原来不在区间内
cnt += 1; //区间内不重复元素个数
b[a[i]]++; //区间内a[i]个数
while(cnt == num) { //区间包括所有内容,这里不用if
if(ans > i - j + 1) ans = i - j + 1;
b[a[j]]--;
if(b[a[j]] == 0) cnt--;
j++; //左边界右移, j++记得放最后
}
}
printf("%d", ans);
return 0;
}
当然,还有一条路,离散化
(2条消息) C++算法——离散化_是挺秃然的齐齐哦的博客-CSDN博客_c++离散化
总结
学习了新的算法思想,尺取法(双指针)
补充了对scanf()和cin的理解
初次了解map和离散化
巩固了队列和快排