A. Mean Inequality
给出一个序列，怎样用这个序列所有的元素构造一个新的数组，使得这个新的数组围成环之后每个数不等于相邻两个数的平均数。
思路： 我们可以从一个比较普遍的情况出发，如果把这个数组升序排序，那很可能在其中存在相邻三个数为等差数列，这必不符合条件。为了防止这种情况，我们可以把升序数列一前一后放入新的数组中，这样整个新数列必为高低高低排列，不存在不满足条件的情况。
AC Code：
#include <bits/stdc++.h>
#pragma GCC optimize(2)
template <typename T>
inline void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0', ch = getchar();
}
x *= f;
}
template <typename T>
void write(T x) {
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
#define INF 0x3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 105;
int t, n;
int a[N];
int main() {
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin >> t;
while (t--) {
std::cin >> n;
for (int i = 1; i <= 2 * n; i++) {
std::cin >> a[i];
}
std::sort(a + 1, a + 1 + 2 * n);
for (int i = 1; i <= n; i++) {
std::cout << a[i] << ' ' << a[2 * n - i + 1] << " \n"[i == n];
}
}
return 0;
}
?B. I Hate 1111
给出一个数，问是否可以表示为11,111,1111，……等的和。
思路：我们可以看出，这一串数中，后面所有的数都是使用若干个11和111求和得到的，因为11%11=0,111%11=1，那就判断n%11的余数乘111与n的大小即可，因为n%11的余数就是若该数可以满足条件使用111的个数。
AC Code：
#include <bits/stdc++.h>
#pragma GCC optimize(2)
template <typename T>
inline void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0', ch = getchar();
}
x *= f;
}
template <typename T>
void write(T x) {
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
#define INF 0x3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int t, n, x;
std::string s;
int main() {
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin >> t;
while (t--) {
std::cin >> n;
int m = n % 11;
std::cout << (m * 111 <= n ? "YES" : "NO") << '\n';
}
return 0;
}
C1. Potions (Easy Version)
?把很多药按顺序摆放，第i个药对生命值的贡献是a[i]，问若要生命值不低于0，最多可以磕多少药。
思路：只要能想到用优先队列就很简单，直接创建降序的优先队列，把每一个贡献加进去，若生命值小于0了，那就把堆顶的元素pop出去，C2一样做法。
AC Code：
#include <bits/stdc++.h>
#pragma GCC optimize(2)
template <typename T>
inline void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0', ch = getchar();
}
x *= f;
}
template <typename T>
void write(T x) {
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
#define INF 0x3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int n, x;
int main() {
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin >> n;
ll res = 0, cnt = 0;
std::priority_queue<int, std::vector<int>, std::greater<int>>pq;
for (int i = 1; i <= n; i++) {
std::cin >> x;
res += x;
cnt++;
pq.push(x);
while (res < 0) {
cnt--;
res -= pq.top();
pq.pop();
}
}
std::cout << cnt << '\n';
return 0;
}
?若有错误请指教，谢谢！
orzorz
