xuhrrr @ 2024-03-01 18:29:52
代码如下：
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <deque>
using namespace std;
struct node{
long long x,id;
};
node a[1000005];
deque <node> q1,q2;
int n,k;
int main()
{
cin >> n >> k;
for(int i = 1 ; i <= n ; ++i){
cin >> a[i].x;
a[i].id = i;
}
for(int i = 1 ; i <= k ; ++i){
if(q1.empty()){
q1.push_back(a[i]);
}
else{
while(!q1.empty() && q1.back().x > a[i].x){
q1.pop_back();
}
q1.push_back(a[i]);
}
}
cout << q1.front().x << " ";
for(int i = k + 1,j = 2 ; i <= n ; ++i,++j){
while(q1.front().id < j){
q1.pop_front();
}
if(q1.empty()){
q1.push_back(a[i]);
}
else{
while(!q1.empty() && q1.back().x > a[i].x){
q1.pop_back();
}
q1.push_back(a[i]);
}
cout << q1.front().x << " ";
}
cout << endl;
for(int i = 1 ; i <= k ; ++i){
if(q2.empty()){
q2.push_back(a[i]);
}
else{
while(!q2.empty() && q2.back().x < a[i].x){
q2.pop_back();
}
q2.push_back(a[i]);
}
}
cout << q2.front().x << " ";
for(int i = k + 1,j = 2 ; i <= n ; ++i,++j){
while(q2.front().id < j){
q2.pop_front();
}
if(q2.empty()){
q2.push_back(a[i]);
}
else{
while(!q2.empty() && q2.back().x < a[i].x){
q2.pop_back();
}
q2.push_back(a[i]);
}
cout << q2.front().x << " ";
}
return 0;
}by xuhrrr @ 2024-03-01 18:30:33
第三个点数据是100 1 780 -645 296 985 957 -342 -47 29 540 654 -28 226 -596 -868 921 -849 -613 -655 946 941 -139 650 -682 682 184 321 -356 611 -349 -21 -481 -524 36 501 -49 -39 176 366 -61 51 -977 356 835 618 -378 -353 -26 825 -165 590 384 -702 281 425 905 909 -377 -358 283 -660 -40 920 79 -809 331 658 -394 656 -63 -626 -180 -322 356 -341 575 282 -17 177 852 553 -609 -727 386 45 149 439 -815 422 -844 466 259 242 -176 -338 -106 -874 354 -668 -834 -860
by __Cby___ @ 2024-03-01 19:24:44
//#include <iostream>
//#include <queue>
//using namespace std;
//struct node {
// int x, y, dis;
//};
//queue<node> q[10], p[10];
//int a[10];
//char mp[1025][1025];
//int dx[4] = { -1,0,1,0};
//int dy[4] = { 0,1,0,-1 };
//int cl[10];
//int n, m, k;
//bool check(int x, int y) {
// if (x<1 || y<1 || x>n || y>m)return 0;
// return 1;
//}
//int main() {
// cin >> n >> m >> k;
// for (int i = 1; i <= k; i++)cin >> a[i];
// int tt = 0;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// cin >> mp[i][j];
// if (mp[i][j] >= '0' && mp[i][j] <= '9') {
// cl[mp[i][j] - '0']++;
// p[mp[i][j] - '0'].push({ i,j,0 });
// }
// if (mp[i][j] == '.')tt++;
// }
// }
// int i = 1;
// int cnt = 0;
// while (1) {
// q[i] = p[i];
// //cout << 112 << endl;
// while (!p[i].empty())p[i].pop();
// while (!q[i].empty()) {
// node t = q[i].front();
// q[i].pop();
// //cout << t.x << " " << t.y <<" "<<t.dis << endl;
// /* for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// cout << mp[i][j] << " ";
// }
// cout << endl;
// }*/
// if (t.dis == a[i]) {
// p[i].push({t.x, t.y,0});
// continue;
// }
// for (int u = 0; u < 4; u++) {
// int wx = t.x + dx[u];
// int wy = t.y + dy[u];
// if (!check(wx, wy))continue;
// if (mp[wx][wy] == '.') {
// //cout << mp[wx][wy] << endl;
// cl[i]++;
// tt--;
// q[i].push({ wx,wy,t.dis + 1 });
// mp[wx][wy] = i+'0';
// if (!tt)break;
// }
// }
// }
// if (!tt)break;
// i = i % k + 1;
// cnt++;
// //cout << i << endl;
// if (cnt >= 10000025)break;
// }
// for (int i = 1; i <= k; i++) {
// cout << cl[i] << " ";
// }
// cout << endl;
// return 0;
//}
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <deque>
using namespace std;
struct node {
long long x, id;
};
node a[1000005];
deque <node> q1, q2;
int n, k;
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i].x;
a[i].id = i;
}
for (int i = 1; i <= k; ++i) {
if (q1.empty()) {
q1.push_back(a[i]);
}
else {
while (!q1.empty() && q1.back().x > a[i].x) {
q1.pop_back();
}
q1.push_back(a[i]);
}
}
cout << q1.front().x << " ";
for (int i = k + 1, j = 2; i <= n; ++i, ++j) {
while (!q1.empty() && q1.front().id < j) {
q1.pop_front();
}
if (q1.empty()) {
q1.push_back(a[i]);
}
else {
while (!q1.empty() && q1.back().x > a[i].x) {
q1.pop_back();
}
q1.push_back(a[i]);
}
cout << q1.front().x << " ";
}
cout << endl;
for (int i = 1; i <= k; ++i) {
if (q2.empty()) {
q2.push_back(a[i]);
}
else {
while (!q2.empty() && q2.back().x < a[i].x) {
q2.pop_back();
}
q2.push_back(a[i]);
}
}
cout << q2.front().x << " ";
for (int i = k + 1, j = 2; i <= n; ++i, ++j) {
while (!q2.empty() && q2.front().id < j) {
q2.pop_front();
}
if (q2.empty()) {
q2.push_back(a[i]);
}
else {
while (!q2.empty() && q2.back().x < a[i].x) {
q2.pop_back();
}
q2.push_back(a[i]);
}
cout << q2.front().x << " ";
}
return 0;
}
by __Cby___ @ 2024-03-01 19:24:59
@xuhrrr 这个是正确的
by __Cby___ @ 2024-03-01 19:25:45
while (q1.front().id < j) {
q1.pop_front();
}变成
while (!q1.empty() && q1.front().id < j) {
q1.pop_front();
}by __Cby___ @ 2024-03-01 19:26:44
while (q2.front().id < j) {
q2.pop_front();
}变成
while (!q2.empty() && q2.front().id < j) {
q2.pop_front();
}by __Cby___ @ 2024-03-01 19:27:14
不然访问 空队列的元素会 RE。
by xuhrrr @ 2024-03-01 19:41:56
@__Cby___ 谢谢大佬，确实没注意到为空的情况