A Mean Inequality

题目大意

给你一个数n和2n个数，把这2n个数凑成一个环，且每个数都不等于左右两边的数的和的一半，求出一个数的排列

主要思路

首先考虑怎么才能让当前数不等于左右两边的数的和的一半，如果左右两边的数都大于或者小于当前数，那么一定不会出现当前数等于左右两边的数的和的一半，所以我们把数组排序，然后取一个最大的数放在第一个位置，取一个最小的数放在第二个位置，取次大的数放在第三个位置…以此类推, 由于题目保证一定有解这种构造方法一定正确

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. using namespace std;
  12. #define int long long
  13. #define debug(a) cout << #a << " = " << a << endl;
  14. #define x first
  15. #define y second
  16. typedef pair<int, int> P;
  18. const int N = 30;
  19. int n, a[2 * N];
  20. int ans[2 * N];
  22. signed main(void)
  23. {
  24.     std::ios::sync_with_stdio(false);
  25.     int T;
  26.     cin >> T;
  27.     while(T--)
  28.     {
  29.         cin >> n;
  30.         for(int i = 0; i < 2 * n; i++) cin >> a[i];
  31.         sort(a, a + 2 * n);
  32.         int cnt = 0;
  33.         for(int i = 0, j = 2 * n - 1; i <= j; i++, j--)
  34.         {
  35.             ans[cnt++] = a[j];
  36.             ans[cnt++] = a[i];
  37.         }
  38.         for(int i = 0; i < 2 * n; i++) cout << ans[i] << ' ';
  39.     }
  40.     return 0;
  41. }

B I Hate 1111

题目大意

有11，111，1111…这些数，给你一个数x，问你是否x能被这些数凑成

主要思路

定理：a和b互质那么他们不能凑出的最大数是a*b-a-b

我们用这个性质算出11和111不能凑出的最大数是1099，那么！！大于1099的数都能凑出来！！

小于1099的直接打表即可

  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. using namespace std;
  12. #define int long long
  13. #define debug(a) cout << #a << " = " << a << endl;
  14. #define x first
  15. #define y second
  16. typedef pair<int, int> P;
  18. const int N = 2010;
  19. int f[N];
  21. signed main(void)
  22. {
  23.     std::ios::sync_with_stdio(false);
  24.     int T;
  25.     cin >> T;
  26.     for(int i = 0; i * 11 <= 1099; i++)//计算出前1099有哪些数能被凑成
  27.     {
  28.         for(int j = 0; i * 11 + j * 111 <= 1099; j++)
  29.         {
  30.             f[i * 11 + j * 111] = 1;
  31.         }
  32.     }
  33.     while(T--)
  34.     {
  35.         int x;
  36.         cin >> x;
  37.         if(x > 1099) puts("YES");
  38.         else
  39.         {
  40.             if(f[x]) puts("YES");
  41.             else puts("NO");
  42.         }
  43.     }
  44.     return 0;
  45. }

C Potions (Hard Version)

C2和C1区别仅为数据范围不同，那么直接冲C2

题目大意

给你n个数，你的初始健康值为0，从左到右选择，你可以选当前数或者不选当前数，唯一的要求是你的健康值不能为负数，问最多能选择的数的个数

主要思路

反悔型贪心。

首先我们用一个小根堆(优先队列)存储当前已经选择的负数的数有哪些。

  • 假设选择当前数后健康值小于0，那么当前数一定是负数，那么我们先选择当前数，并且放入优先队列中，然后在优先队列中找出负数中最小的数，并且不选择此数即可
  • 假设选择当前数后健康值大于等于0，那么也选择这个数，如果该数为负数，则放入优先队列
  1. #include <iostream>
  2. #include <cstring>
  3. #include <string>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <string>
  7. #include <cmath>
  8. #include <unordered_map>
  9. #include <queue>
  10. using namespace std;
  12. #define int long long
  13. #define debug(a) cout << #a << " = " << a << endl;
  14. #define x first
  15. #define y second
  16. typedef pair<int, int> P;
  18. const int N = 200010;
  19. int f[N][2], g[N][2], a[N], n;
  21. signed main(void)
  22. {
  23.     std::ios::sync_with_stdio(false);
  24.     cin >> n;
  25.     for(int i = 0; i < n; i++) cin >> a[i];
  27.     priority_queue<int, vector<int>, greater<int>> q;
  28.     int res = 0;
  29.     int s = 0;
  30.     for(int i = 0; i < n; i++)
  31.     {
  32.         if(s + a[i] < 0)
  33.         {
  34.             q.push(a[i]);
  35.             s += a[i];
  36.             int t = q.top();
  37.             s -= t;
  38.             q.pop();
  39.         }
  40.         else
  41.         {
  42.             s += a[i];
  43.             res++;
  44.             if(a[i] < 0) q.push(a[i]);
  45.         }
  46.     }
  47.     cout << res << endl;
  48.     return 0;
  49. }

D题放一放，会了再补充！