蓝桥杯--快排+队列+尺取法

😃这只松鼠如约而至 - 许嵩 - 单曲 - 网易云音乐 

😃你买菜吗玫瑰 - 要不要买菜 - 单曲 - 网易云音乐 

😃一起玩吧这世界那么多人（电影《我要我们在一起》主题曲） - 莫文蔚 - 单曲 - 网易云音乐 

前言

这是我在CSDN做算法技能树遇到的第一个卡点，接着又在POJ找了道类似题目,挺综合的

刚好学了快排，队列，尺取法(也叫双指针,是一种算法思想,用的原理就是队列),就练练手呗

杰西卡是日志统计的进阶版本

日志统计

P1373 - [蓝桥杯2018初赛]日志统计 - New Online Judge (ecustacm.cn) 

题目1地址：(代码选择题,数据量达10^5)

日志统计-蓝桥杯-基础-CSDN算法技能树

题目 

如果填空题 --> 代码题,我们该怎么做呢

 

思路

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数组标记热帖

AC  38%

#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].idprintf("%d\n", i);return 0;
}

AC  100% 

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
typedef pair<int, int> PII;
#define x first
#define y second
PII logs[N];
bool st[N];
int cnt[N];int main()
{int n, d, k;cin >> n >> d >> k;for (int i = 0; i < n; i++)cin >> logs[i].x >> logs[i].y;sort(logs, logs + n);for (int i = 0, j = 0; i < n; i++){cnt[logs[i].y]++;while (logs[i].x - logs[j].x >= d)cnt[logs[j].y]--, j++;if (cnt[logs[i].y] >= k)st[logs[i].y] = true;}for (int i = 0; i < N; i++)if (st[i])cout << i << endl;return 0;
}

 

杰西卡的阅读问题

  不容易,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，快排

3，scanf()比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)); //初始化数组bfor(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) { //区间包括所有内容,这里不用ifif(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; //初始化bfor(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) { //区间包括所有内容,这里不用ifif(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和离散化

巩固了队列和快排