Skip to content

11034: 【原1034】二哥的金链

题目

题目描述

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

Description

一个阳光明媚的周末,二哥出去游山玩水,然而粗心的二哥在路上把钱包弄丢了。傍晚时分二哥来到了一家小旅店,他翻便全身的口袋也没翻着多少钱,而他身上唯一值钱的就是一条漂亮的金链。这条金链散发着奇异的光泽,据说戴上它能保佑考试门门不挂,RP++。好心的老板很同情二哥的遭遇,同意二哥用这条金链来结帐。虽然二哥很舍不得这条金链,但是他必须用它来付一晚上的房钱了。

金链是环状的,一共有 N 节,老板的要价是 K 节。随便取下其中 K 节自然没问题,然而金链上每一节的 RP 值其实并不一样,有高有低,二哥自己非常清楚。另外二哥并不希望把整个金链都拆散了,他只愿意在这条环形的金链上切两刀,从而切下一段恰好为 K 节的金链给老板。因为 RP 值越高的节越稀有,因此他希望给老板的金链上最高的 RP 值最小。

Input Format

第一行两个整数 N 和 K,表示金项链有 N 节,老板要价 K 节。

第二行用空格隔开的N个正整数 a1...aN ,表示每一节金链的价值为多少。

Output Format

输出一个整数,表示二哥给老板的金链上最高的 RP 值最小多少。

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

说明

对40%的数据,\( 3 \leq N \leq 200 \) ;

对70%的数据,\( 3 \leq N \leq 20000 \);

对100%的数据,\( 3 \leq N \leq 200000 \) , \( 0 < ai \leq 10^9 \)。

数据规模较大,建议用scanf("%d", &a[i]);来读数据。

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++) {
        pq.push(head + 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 a[300000],rp[300000],n,k,head,tail,minrp=0x3f3f3f3f;
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){
        while (head>0&&rp[a[head-1]]<=rp[i]) head--;
        a[head++]=i;
    }
    if (rp[a[tail]]<minrp) minrp=rp[a[tail]];
    for (int i=k;i<n;++i){
        while (head>tail&&a[tail]<=i-k) tail++;
        while (head>tail&&rp[a[head-1]]<=rp[i]) head--;
        a[head++]=i;
        if (rp[a[tail]]<minrp) minrp=rp[a[tail]];
    }
    for (int i=0;i<k-1;++i){
        while (head>tail&&(a[tail]>i&&a[tail]<=i-k+n)) tail++;
        while (head>tail&&rp[a[head-1]]<=rp[i]) head--;
        a[head++]=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;
}