题意：
一个集合S的优美值定义为：最大的x，满足对于任意i∈[1,x]，都存在一个S的子集S'，使得S'中元素之和为i。
给定n个集合，对于每一次询问，指定一个集合S1和一个集合S2，以及一个数k，要求选择一个S2的子集S3(|S3|<=k)，使得S1∪S3的优美值最大。
（集合元素可以重复）
Input
第一行一个数n，（n<=1000）
接下来n行，每行描述一个集合：
第一个数m，表示集合大小，接下来m个数，表示集合中的元素（m<=1000，元素<=10^9）
第n+2行一个数T，表示询问次数（T<=10000）
接下来T行，每行3个数a，b，k，表示指定第a个集合为S1，第b个集合为S2，k的意义如题（a<=n,b<=n,k<=100,000）
Output
T行，每行一个数，表示对应询问所能达到的最大优美值
Input示例
2
6 1 2 3 8 15 32
6 1 1 1 1 1 1
1
1 2 3
Output示例
64
思路：
好题。
很关键的一点要发现一个事实，那就是如果当前我们可以通过a集合的数组合满足[1,sum]之内的数都能找出子集达到，当前需要判断的数是a[i]，如果sum >= a[i] - 1，那么[1, sum + a[i] ]之内的数都能满足条件。
但是如果sum < a[i] - 1，这时候就要借助b集合的数了，这里处理的思路也是一样的，如果我们能在b集合中找到满足 sum >= y - 1 的最大的y，就可以保证在[1, sum + y]中所有的数都能达到，这样我们只要在b集合中不断寻找符合的y即可，直到此时sum >= a[i] - 1或者k次机会用光了，就退出。同理，如果a集合中所有的元素都已经判断过了，此时k次机会如果还有剩余，那么就要继续上述过程，不断扩大sum，直到用光k次。
这时候最关键的就是如何找到 y了，很显然二分是可以考虑的，但是这里不能重复利用，所以每次用了一个y，就应该将其从b集合中删除，一开始我用的是multiset来存储集合，直接erase删除，但是T了。看了大神的解法，发现居然可以用并查集！！
并查集的思路是这样的，一开始排好序的b集合中所有的序号都是不相连的，如果我们每次找到一个y，其序号是id，用了y之后，下一次二分就不应该找y了，应该找比y更小的，所以在使用了y之后需要讲其id和前一个id-1进行合并操作，使id的祖先为id-1的祖先(这里很关键，不能搞反顺序！)，这样每次二分出一个y，我们就要通过并查集find它的祖先，因为它的祖先是可以被利用的，如果find的结果为0，说明比y小的都不能被用，这时候就break。
具体细节，看代码，因为用了vector，下标从0~n-1，但是并查集的下标仍然是1~n，这里p[i]表示的就是序号i-1。
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int MAXN = 1005;
vector <int> vec[MAXN];
multiset <int> :: iterator it;
inline bool scan_d(int &num) {
char in;
bool IsN = false;
in = getchar();
if (in == EOF) return false;
while (in != '-' && (in < '0' || in > '9')) in = getchar();
if (in == '-'){ IsN = true; num = 0;}
else num = in - '0';
while (in = getchar(), in >= '0' && in <= '9') {
num *= 10, num += in - '0';
}
if (IsN) num = -num;
return true;
}
void Out(long long a) { //输出外挂
if (a < 0) { putchar('-'); a = -a; }
if (a >= 10) Out(a / 10);
putchar(a % 10 + '0');
}
int pa[MAXN];
void init(int n) {
for (int i = 0; i <= n; i++) pa[i] = i;
pa[n + 1] = n;
}
int Find(int x) {
return pa[x] == x ? x : pa[x] = Find(pa[x]);
}
void combine(int x, int y) {
int px = Find(x), py = Find(y);
pa[py] = px;
}
int main() {
//freopen("in.txt", "r", stdin);
int n, m, t, x;
scan_d(n);
for (int i = 1; i <= n; i++) {
scan_d(m);
for (int j = 1; j <= m; j++) {
scan_d(x);
vec[i].push_back(x);
}
sort(vec[i].begin(), vec[i].end());
}
scan_d(t);
while (t--) {
int a, b, k;
scan_d(a); scan_d(b); scan_d(k);
init(vec[b].size());
long long sum = 0;
int cnt = 0;
for (int i = 0; i < (int)vec[a].size(); i++) {
if (sum >= vec[a][i] - 1) {
sum += vec[a][i];
}
else {
while (cnt < k && sum < vec[a][i] - 1) {
int id = upper_bound(vec[b].begin(), vec[b].end(), sum + 1) - vec[b].begin();
id = Find(id);
if (id <= 0) break;
sum += vec[b][id - 1];
combine(id - 1, id);
++cnt;
}
if (sum < vec[a][i] - 1) break;
sum += vec[a][i];
}
}
while (cnt < k) {
int id = upper_bound(vec[b].begin(), vec[b].end(), sum + 1) - vec[b].begin();
id = Find(id);
if (id <= 0) break;
sum += vec[b][id - 1];
combine(id - 1, id);
++cnt;
}
Out(sum);
puts("");
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-3903.html
