Gym 101170F Free Weights（二分）题解

素颜马尾好姑娘i 2021-12-20 04:53 173阅读 0赞

题意：给出两行，每一行都有n个数组，一共有2 \* n个，大小为1~n，每个有两个。现在可以进行操作：拿出一个物品i，然后放到一个空格，花费i。可以任意平移物品，平移没有花费。每一行空间无限。要求你把一样的数字要放在相邻位置，即1 1放一起，2 2放一起...问你你所有拿出的物品的最大花费max\{ i \}最小是多少。比如，我拿了1 2 3，那么最大花费max\{ i \}最小是3。

思路：我们二分这个答案m，显然比m小的可以直接移到末尾的无限空间，所以只要判断比m大的有没有成双成对就行。

打的时候居然没有想到！！！

代码：

#include<stack>
    #include<set>
    #include<map>
    #include<queue>
    #include<cstdio>
    #include<vector>
    #include<cstring>
    #include <iostream>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    const int maxn = 1e6 + 10;
    const ull seed = 131;
    const int INF = 0x3f3f3f3f;
    const int MOD = 1e9 + 7;
    int n, w1[maxn], w2[maxn];
    bool check(int m){
        stack<int> s;
        while(!s.empty()) s.pop();
        for(int i = 1; i <= n; i++){
            if(w1[i] > m){
                if(s.empty()) s.push(w1[i]);
                else if(!s.empty() && s.top() == w1[i]) s.pop();
                else return false;
            }
        }
        if(!s.empty()) return false;
        for(int i = 1; i <= n; i++){
            if(w2[i] > m){
                if(s.empty()) s.push(w2[i]);
                else if(!s.empty() && s.top() == w2[i]) s.pop();
                else return false;
            }
        }
        if(!s.empty()) return false;
        return true;
    }
    int main(){
        scanf("%d", &n);
        int Max = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d", &w1[i]);
            Max = max(Max, w1[i]);
        }
        for(int i = 1; i <= n; i++){
            scanf("%d", &w2[i]);
            Max = max(Max, w2[i]);
        }
        int l = 0, r = Max;
        int ans = INF;
        while(l <= r){
            int m = (l + r) >> 1;
            if(check(m)){
                ans = m;
                r = m - 1;
            }
            else{
                l = m + 1;
            }
        }
        printf("%d\n", ans);
        return 0;
    }

转载于:https://www.cnblogs.com/KirinSB/p/10878430.html