# 11034: 【原1034】二哥的金链

### 题目描述

author: bsearch 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1034

## Sample Input

5 2
1 2 3 4 5


## Sample Output

2


## Sample Input

6 3
1 4 7 2 8 3


## Sample Output

4


## BugenZhao's solution

//
// Created by BugenZhao on 2019/3/23.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <list>

using namespace std;

using ll=long long;
using Pair=pair<int, int>;

int main() {
priority_queue<Pair> q;
int N, K;
cin >> N >> K;
int values[400005];
for (int i = 0; i < N; ++i) {
scanf("%d", values + i);
}
for (int l = 0; l < K; ++l) {
values[N + l] = values[l];
}
for (int j = 0; j < K; ++j) {
q.push(Pair(values[j], j));
}
int maxAns = q.top().first;
Pair tmp;
for (int k = K; k < N + K; ++k) {
q.push(Pair(values[k], k));
tmp = q.top();
while (tmp.second < k - (K - 1)) {
q.pop();
tmp = q.top();
}
maxAns = min(maxAns, q.top().first);
}
cout << maxAns << endl;
return 0;
}


## FineArtz's solution

/* 二哥的金链 */
#include <iostream>
#include <deque>
using namespace std;

void pop_back(deque<int> &d){
while ((d.end() - d.begin()) >= 1 && d.back() >= d.front())
d.pop_front();
if (!d.empty()) d.pop_back();
}

int main(){
int n, k, a[400005];
cin >> n >> k;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = n + 1; i <= n + k; ++i)
a[i] = a[i - n];
deque<int> f, ff;
for (int i = 1; i <= k; ++i)
{
while (!f.empty() && a[i] > f.back()){
pop_back(f);
}
f.push_back(a[i]);
ff.push_back(a[i]);
}
int maxmin = f[0];
for (int i = k + 1; i <= n + k; ++i){
while (!f.empty() && a[i] > f.back()){
pop_back(f);
}
f.push_back(a[i]);
if (f[0] == ff[0]) f.pop_front();
ff.pop_front();
ff.push_back(a[i]);
if (maxmin > f[0]) maxmin = f[0];
}
cout << maxmin << endl;
return 0;
}


## ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

int val[400009] = { 0 };
//单调队列类
class f_queue {
public:
//存储单调队列数据的数组
int queue_data[400009] = { 0 };
//队头元素位置
int start = 0;
//队尾元素位置
int end = 0;
//插入函数
void push(int num) {
int i = end;
//从队尾开始扫描，将小于num的元素全部弹出，直到遇到大于等于num的元素
for (; i > start; --i) {
if (queue_data[i - 1] >= num)
break;
}
//将num放入单调队列中
queue_data[i] = num;
end = i + 1;
}
//弹出函数
void pop(int num) {
//判断需要弹出的num是否与队头元素相等，如果相等则将队头出队，如果不相等则不进行任何操作
if (num == queue_data[start])
++start;
}
//返回队头元素
int front() {
return queue_data[start];
}
};

//单调队列
f_queue qdata;

int main() {
int N, K;
cin >> N >> K;

int init = 0;
for (int i = 0, cur_max = 0; i < N; ++i) {
scanf("%d", &val[i]);
}

//拼接，并且将前K个元素入单调队列
for (int i = 0; i < K; ++i) {
val[N + i] = val[i];
qdata.push(val[i]);
}

int rp_max = qdata.front();
for (int i = 0; i < N; ++i) {
//移动窗口，先将第i个元素出单调队列，再将第i+K个元素入队，并判断此时单调队列中的最大值是否比rp_max小
qdata.pop(val[i]);
qdata.push(val[i + K]);
if (qdata.front() < rp_max)
rp_max = qdata.front();
}
//输出答案rp_max
cout << rp_max;

return 0;
}


## LuminousXLB's solution

// 1034. 二哥的金链
// #464985 正确 / 分数：100 / 时间：212ms / 内存：13916kb

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

class mycomparison {
bool reverse;
public:
mycomparison(const bool& revparam = false) {
reverse = revparam;
}
bool operator()(int *& lhs, int *& rhs) const {
if (reverse) {
return(*lhs > *rhs);
} else {
return(*lhs < *rhs);
}
}
};

typedef std::priority_queue<int *, std::vector<int *>, mycomparison> mypq;

int *findmax(int *head, int len) {
mypq pq;

for (size_t i = 0; i < len; i++) {
}

return pq.top();
}

int main(int argc, char const *argv[]) {
// freopen("sample.in", "r", stdin);

size_t count, len;
int *rp = new int[count + len];

scanf("%d %d", &count, &len);
for (size_t i = 0; i < count; i++) {
scanf("%d", &rp[i]);
}

for (size_t i = 0; i < len; i++) {
rp[i + count] = rp[i];
}

mypq pq(mycomparison(true));
int *bottom = rp + count;
for (int *p = rp; p < bottom; p++) {
p = findmax(p, len);
pq.push(p);
}

printf("%d\n", *pq.top());

return 0;
}


## skyzh's solution

#include <iostream>
#include <map>
#include <cstdio>
#include <climits>
using namespace std;

int main() {
int N, K;
// still thinking of a better solution without map QwQ
map <int, int> m;
int data[200000];
scanf("%d%d", &N, &K);
for (int i = 0; i < N; i++) {
scanf("%d", &data[i]);
}
for (int i = 0; i < K; i++) m[data[i]]++;
int _min = INT_MAX;
for (int i = K, j = 0; j < N; j++) {
auto iter = m.rbegin();
while (iter->second == 0) ++iter;
_min = min(_min, iter->first);
m[data[j]]--;
m[data[i]]++;
if (++i >= N) i -= N;
}
printf("%d\n", _min);
return 0;
}


## WashSwang's solution

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
scanf("%d%d",&n,&k);
for (int i=0;i<n;++i)
scanf("%d",&rp[i]);
for (int i=0;i<k;++i){
}
if (rp[a[tail]]<minrp) minrp=rp[a[tail]];
for (int i=k;i<n;++i){
if (rp[a[tail]]<minrp) minrp=rp[a[tail]];
}
for (int i=0;i<k-1;++i){
if (rp[a[tail]]<minrp) minrp=rp[a[tail]];
}
printf("%d",minrp);
return 0;
}


## yyong119's solution

#include <iostream>
#include <cstdio>
using namespace std;
int n, k, i, maxnum, minnum, mid, countn;
int a[200001];
bool flag;
int main() {
scanf("%d%d", &n, &k);
minnum = 1000000001;
for (i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i + n] = a[i];
maxnum = max(maxnum, a[i]);
minnum = min(minnum, a[i]);
}
while (minnum < maxnum) {
mid = (minnum + maxnum) / 2;
countn = 0; flag = false;
for (i = 1; i <= 2*n; i++) {
if (countn == k) { flag = true; break; }
if (a[i] <= mid) countn++; else countn = 0;
}
if (flag) maxnum = mid; else minnum = mid + 1;
}
printf("%d\n", (minnum + maxnum) / 2);
return 0;
}