题意：给定\(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\)，不合题意
所以枚举右端点，直接一路扫过去即可。
当然同理也可以把中间的元素丢到两边，所以答案也可以是一个前缀+一个后缀
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#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>(); } |
说点什么