【IOI2016】检测分子 – 徐亦轲的博客

题意：给定\(n\)个正整数\(w_{1…n}\)，从中找出一些数的和在给定区间\([l,u]\)内。

保证\(u-l\ge w_{max}-w_{min}\)。

将原数列排序，那么答案一定是一段连续的区间。

假设存在一个解不是一段连续的区间，当我们选择中间一个元素时，一定可以丢掉两边的元素之一使得和仍然在区间内。

否则有\(sum+w_p-w_r<l\)，\(sum+w_p-w_l>u\)

那么有\(u+w_l<l+w_r\)，即\(u-l\le w_r-w_l\)，不合题意

所以枚举右端点，直接一路扫过去即可。

当然同理也可以把中间的元素丢到两边，所以答案也可以是一个前缀+一个后缀

#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lol;
vector<int> ans;
int ww[200010],id[200010];
bool cmp(int x,int y){return ww[x]<ww[y];}
vector<int> find_subset(int l, int u, vector<int> w) {
    int n=w.size(),p=0;
    for(int i=0;i<n;i++)ww[i]=w[i],id[i]=i;
    sort(id,id+n,cmp);
    lol sum=0;
    for(int i=0;i<n;i++){
        sum+=w[id[i]];
        while(sum>u)sum-=w[id[p++]];
        if(sum>=l){
            for(int j=p;j<=i;j++)ans.push_back(id[j]);
            return ans;
        }
    }
    return vector<int>();
}

#include "molecules.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long lol;

vector<int> ans;

int ww[200010],id[200010];

bool cmp(int x,int y){return ww[x]<ww[y];}

vector<int> find_subset(int l, int u, vector<int> w) {

int n=w.size(),p=0;

for(int i=0;i<n;i++)ww[i]=w[i],id[i]=i;

sort(id,id+n,cmp);

lol sum=0;

for(int i=0;i<n;i++){

sum+=w[id[i]];

while(sum>u)sum-=w[id[p++]];

if(sum>=l){

for(int j=p;j<=i;j++)ans.push_back(id[j]);

return ans;

}

return vector<int>();

}

说点什么