代码如下:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int _, n, p, a[N];
set<pair<int, int> > st;
set<pair<int, int> >::iterator it;
inline void READDATA(int cas) {
scanf("%d", &n);
if (cas == 1) {
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
} else {
for (int i = 1; i <= n; ++i) {
scanf("%d", &p); scanf("%d", a + p);
}
}
return;
}
int PROCESSDATA() {
if (n <= 3) { // 保分
if (a[3] >= a[1] + a[2]) return 1;
return 3;
}
st.clear();
for (int i = 1; i <= n; ++i) st.insert({a[i], i}); // 插入数据
int size = 0, ans = 0; // size 存储大小
while (1) {
if (st.size() == 2) { // comes to an end
st.erase(st.begin());
if (size) {
ans = size + (size - st.size()) % 2;
} else ans = 1;
break;
}
it = st.end(); --it;
int num = it->first, id = it->second;
int minn = st.begin()->first;
st.erase(it), st.erase(st.begin());
st.insert({num - minn, id});
if (st.begin()->second != id) {
if (size) {
ans = size + (size - st.size()) % 2;
break;
}
} else if (size == 0) size = st.size();
}
}
int main() {
scanf("%d", &_);
for (int cas = 1; cas <= _; ++cas) {
READDATA(cas);
printf("%d\n", PROCESSDATA());
}
}