ACM模版
描述
题解
这个题当时我没看懂题,所以没做,后续补题时学到了很多东西~~~好题!
题意大概是,从 A[] 和 B[] 中对应位置分别取不超过 ⌊n2⌋+1 个数,使分别对于 A[] 和 B[] 来说,这些数之和的二倍大于该数组和,也就是说子集的两倍大于数组和,那么等价于所取的数之和大于未取的数之和,所以,这里自然是取数越多越好,最多 ⌊n2⌋+1 个。
这里由于结果不唯一,所以这是一个特判题。这样也就催生出了一种玄学的解法(代码 One),通过随机乱序原数组,然后判断前 ⌊n2⌋+1 个数的和是否满足题意,不满足继续乱序,一直到碰应了结果就输出,GG。这个有些许猴子排序的恶搞趣味,但是你没有看错,这里能够 AC。据我猜测这个之所以可行是因为可行解十分多,所以他乱序碰到答案的可能性比较高,如果对于可行解不多的题,那么这就是贴脸草题,有些考验脸了。
当然,还有比较客观的解法(代码 Two),先根据 A[] 对 pos 排序,然后将最大的入 ans,接着每两个进行一次判断,看哪个 B[] 大,大的入 ans,这样遍历一遍后就是结果了。这里需要强调的一点是必须先将最大的入 ans,不然无法保证 A 的合法性,只有先将最大的入了 ans,才能保证下次未选取的数一定小于上一次选取的数,例如,1,4,6,8,9,我们先将 9 入 ans,然我们不管在 (6,8) 中选取哪个,那个未被选取的都一定小于 9,接着在 (1,4) 中不管选哪个,那个未被选取的都要比上一个选取的数(6 或 8)小,这就可以保证 A 的合法性。
另外,这个客观的解法需要定义一个三元结构体,分别存储 a, b, pos,在网上看到了一个我没有用过的数据结构来直接搞,十分方便,叫做元组,<
tuple
>,类似于结构体,十分强大,这里我也提供一下利用元组的解法(代码 Three)。
代码
One:
#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;
typedef long long ll;
const int MAXN = e5 + ;
int n;
int pos[MAXN];
int a[MAXN], b[MAXN];
ll sumA, sumB;
int main(int argc, char const *argv[])
{
scanf("%d", &n);
for (int i = ; i < n; i++)
{
scanf("%d", a + i);
sumA += a[i];
a[i] <<= ;
pos[i] = i;
}
for (int i = ; i < n; i++)
{
scanf("%d", b + i);
sumB += b[i];
b[i] <<= ;
}
int mid = n / + ;
srand((int)time());
while ()
{
ll s1 = , s2 = ;
random_shuffle(pos , pos + n);
for (int i = ; i < mid; i++)
{
s1 += a[pos[i]];
s2 += b[pos[i]];
}
if (s1 > sumA && s2 > sumB)
{
printf("%d\n%d", mid, pos[] + );
for (int i = ; i < mid; i++)
{
printf(" %d", pos[i] + );
}
puts("");
return ;
}
}
return ;
}
Two:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = + ;
struct abpos
{
int a;
int b;
int pos;
};
abpos c[MAXN];
vector<int> ans;
int n;
int a[MAXN], b[MAXN];
bool cmp(abpos a, abpos b)
{
return a.a < b.a;
}
int main()
{
cin >> n;
for (int i = ; i <= n; i++)
{
cin >> a[i];
}
for (int i = ; i <= n; i++)
{
cin >> b[i];
}
c[].a = c[].b = c[].pos = ;
for (int i = ; i <= n; i++)
{
c[i].a = a[i];
c[i].b = b[i];
c[i].pos = i;
}
sort(c + , c + n + , cmp);
ans.push_back(c[n].pos);
for (int i = n - ; i >= ; i -= )
{
if (c[i].b > c[i - ].b)
{
ans.push_back(c[i].pos);
}
else
{
ans.push_back(c[i - ].pos);
}
}
cout << ans.size() << endl;
for (int i = ; i < ans.size(); i++)
{
cout << ans[i] << ' ';
}
return ;
}
Three:
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
typedef tuple<int, int, int> tp;
const int MAXN = + ;
tp tpThree[MAXN];
vector<int> ans;
int n;
int a[MAXN], b[MAXN];
int main()
{
cin >> n;
for (int i = ; i <= n; i++)
{
cin >> a[i];
}
for (int i = ; i <= n; i++)
{
cin >> b[i];
}
for (int i = ; i <= n; i++)
{
tpThree[i] = tp(a[i], b[i], i);
}
tpThree[] = tp(, , );
sort(tpThree + , tpThree + n + );
int pos;
tie(ignore, ignore, pos) = tpThree[n];
ans.push_back(pos);
int y, y_, pos_;
for (int i = n - ; i >= ; i -= )
{
tie(ignore, y, pos) = tpThree[i];
tie(ignore, y_, pos_) = tpThree[i - ];
if (y > y_)
{
ans.push_back(pos);
}
else
{
ans.push_back(pos_);
}
}
cout << ans.size() << endl;
for (int i = ; i < ans.size(); i++)
{
cout << ans[i] << ' ';
}
return ;
}