题解 P6169 [IOI2016] molecules

gznpp · 2020-12-02 15:42:12 · 题解

题意：给定 N 个数的集合 A，求出一个子集满足它的和在 [L, R] 内。

特殊性质：R - L \ge \max A - \min A。

暴力：当然可以用 bitset 优化背包做，时间复杂度 O(\dfrac{NW}{64})，貌似可以过 Subtask 5。

这完全没有考虑特殊性质，而这正是正解不同之处。我们来探究一下它到底表达了什么。

正解：猜想对序列排序之后，答案可以是一个线段。

因为只要丢掉一个线段左侧的元素再增加一个右侧的元素，对答案的影响一定不超过 \max A - \min A，也就不超过 R - L，一定不会错过答案。

实现时先一路取前缀到和 \le L，然后模拟前面过程即可。复杂度瓶颈是排序的 O(N \log N)，双指针 O(N)。

Code:

#include <bits/stdc++.h>
#include "molecules.h"
#define rgi register int
#define ll long long
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
using namespace std;
int n;
ll s,L,R;
vector<int> ans;
vector<pii> a;
vector<int> find_subset(int LL,int RR,vector<int> w)
{
    n=w.size();
    L=LL,R=RR;
    for(rgi i=0;i<n;++i)
        a.push_back(mkp(w[i],i));
    sort(a.begin(),a.end());
    for(rgi l=0,r=0;l<n;++l)
    {
        while(s<L&&r<n)
            s+=(ll)a[r++].fi;
        if(s>=L&&s<=R)
        {
            for(rgi i=l;i<r;++i)
                ans.push_back(a[i].se);
            return ans;
        }
        s-=a[l].fi;
    }
    return vector<int>();
}

官方题解还有一种做法，就是答案可以是一段前缀加一段后缀。

其实道理是一样的，先把前缀取完然后慢慢减前缀长度加后缀后缀长度即可，每次移动也不会超过 \max A - \min A \le R - L，不会错过答案。

Code:

#include <bits/stdc++.h>
#include "molecules.h"
#define rgi register int
#define ll long long
#define pii pair<int,int>
#define mkp make_pair
#define fi first
#define se second
using namespace std;
int n;
ll s,L,R;
vector<int> ans;
vector<pii> a;

vector<int> find_subset(int LL,int RR,vector<int> w) {
    n = w.size(); a.resize(n);
    L = LL, R = RR;
    for (int i = 0; i < n; ++i) {
        a[i].fi = w[i];
        a[i].se = i;
        s += (ll)w[i];
    }
    sort(a.begin(), a.end());
    for (int i = n - 1, j = n; i < j && i >= -1;) { // interval [0, i] \cup [j, n - 1]
        while (s > R && i >= 0) {
            s -= (ll)a[i].fi;
            --i;
        }
        if (L <= s && s <= R) {
            for (int k = 0; k <= i; ++k) ans.push_back(a[k].se);
            for (int k = j; k < n; ++k) ans.push_back(a[k].se);
            return ans;
        }
        --j;
        s += (ll)a[j].fi;
    }
    return vector<int>();
}