时间来不及没写完,还是记录一下题目原型,只测试了样例。
原型大概是有n(20w)个基站,每个基站有一个海拔a[i]。有q(20w)个查询,每个查询是一场洪水,海拔小于洪水高度的基站会被淹没,然后剩下的基站相连的可以形成一个集群。每一场洪水是独立的,问每个查询对应有几个集群。
由于输入和查询都比较大,如果使用O(N*Q)的暴力查询一定是超时的。我们可以把离线排序洪水高度,假设第k高的洪水的集群数是确定的,那么第k+1高的洪水其实只要check一下k~k+1之间的基站,然后淹没掉就可以了,淹没的时候check一下该基站的左右两侧来更新集群数。而k~k+1的基站我们可以一开始记录基站的index,然后按照高度排序。这样就可以用二分快速找到k~k+1基站的位置。这样计算下来,时间复杂度大概是O(QlogN+N)
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
struct DATA{
int value;
int index;
DATA(){value=0; index=0;}
DATA(int a, int b):value(a), index(b){}
};
DATA arr[N];
struct QUERY{
int value;
int index;
int res;
QUERY(){value=0; index=0; res=0;}
QUERY(int a, int b, int c):value(a), index(b), res(c){}
};
QUERY query[N];
int block[N] = {0};
int main() {
int n, q, x;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> arr[i].value;
arr[i].index = i;
}
sort(arr, arr+n, [](const DATA& a, const DATA& b) {
return a.value < b.value;
});
cin >> q;
for(int i = 0; i < q; i++) {
cin >> query[i].value;
query[i].index = i;
query[i].res = 1;
}
// 查询值从小到大排序
sort(query, query+q, [](const QUERY& a, const QUERY& b) {
return a.value < b.value;
});
size_t last_fill_pos = 0;
for(int i = 0; i < q; ++i) {
if(i > 0) query[i].res = query[i-1].res;
// 二分查找a中>query[i]的位置
DATA key(query[i].value, 0);
size_t safe_pos = upper_bound(arr+last_fill_pos, arr + n, key, [](const DATA& a, const DATA& b){
return a.value < b.value;
}) - arr;
// 小于idx的位置全部淹没。
while(last_fill_pos < safe_pos) {
int pos = arr[last_fill_pos].index;
// check block
if((pos - 1 >= 0 && block[pos-1] == 0) && (pos+1 < n) && block[pos+1] == 0) {
query[i].res ++;
}
if((pos - 1 >= 0 && block[pos-1] == 1) && (pos+1 < n) && block[pos+1] == 1) {
query[i].res --;
}
if(pos == 0 && block[pos+1] == 1 || pos == n-1 && block[pos-1] == 1) {
query[i].res --;
}
block[pos] = 1;
last_fill_pos++;
}
}
// 查询按照输入排序
sort(query, query+q, [](const QUERY& a, const QUERY& b) {
return a.index < b.index;
});
for(int i = 0; i < q; i++) {
cout << query[i].res << endl;
}
// system("pause");
return 0;
}
// 10
// 6 12 20 14 15 15 7 19 18 13
// 6
// 15 23 19 1 17 24
补充:
还有一题也记录下,题意大概是给定一个字符串,至多修改两次使得包含字符全为N的子串的长度最大,求出长度。
这题之前做过类似的,是百度的最后一题,是求一个二进制串最多修改k次,使得1串最长。直接按照原来的代码写的,
但是看原来的代码还是有点奇怪。所以重新写下,也是没有测试,希望下次能遇到原题测一下。
大概的方法就是两个下标,一个下标前进,当前进的下标无法前进时(即k次修改机会也用完时),那么后一个下标前进,把修改机会让出来。这里用了一个数据结构保存被修改的下标的下一个位置,这样可以再无法前进时,快速调整后一个下标。
#include<bits/stdc++.h>
using namespace std;
int max_same_str(const string& str, char s_chr, int k) {
// 非s_chr串的下一个位置
queue<int> fast_jump;
// 滑窗左右边界(闭区间)
int left = 0, right =0;
int len = str.size();
int max_ch_cnt = 0;
while(right < len) {
// 滑动右边界
if(str[right] == s_chr || k > 0) {
if(str[right] != s_chr) {
fast_jump.push(right+1);
--k;
}
++right;
}
else {
// 收缩左边界
max_ch_cnt = max(max_ch_cnt, right-left);
left = fast_jump.front();
fast_jump.pop();
++k;
}
}
max_ch_cnt = max(max_ch_cnt, right-left);
return max_ch_cnt;
}
int main() {
string str;
int k;
cin >> k;
while(k--) {
cin >> str;
cout << max_same_str(str, 'N', 2) << endl;
}
// system("pause");
return 0;
}
// 3
// NNTN
// NNNNGGNNNN
// NGNNNNGNNNNNNNNSNNNN
本文由 shinelin 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Aug 11, 2019 at 01:07 pm