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;
}