VP*5;
A. Construct a Rectangle
给出三根木棒，任意断开一根，要满足所得到的木棒长度都是整数，且四根木棒可以组成一个矩形，问是否可以按照要求组成这样一个矩形。
思路： 分情况讨论，我们可以知道只能断开长度最长或者长度最短的一根，分情况讨论即可。
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)
print(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 = 1e5 + 5;
int t, a[4];
int main() {
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
std::cin >> t;
while (t--) {
std::cin >> a[1] >> a[2] >> a[3];
std::sort(a + 1, a + 1 + 3);
if (a[3] == a[1] + a[2])
std::cout << "YES" << '\n';
else if (a[2] == a[3] && a[1] % 2 == 0)
std::cout << "YES" << '\n';
else if (a[2] == a[1] && a[3] % 2 == 0)
std::cout << "YES" << '\n';
else
std::cout << "NO" << '\n';
}
return 0;
}B. Berland Music
一开始给出一个含有1~n的数列，现在给出一个01子串，1对应的原数字一定要大于0对应的，问怎样构造使得花费最少，花费是指一个数到赋值后的差。
思路：将0对应的数字拿出来，1对应的拿出来，0对应的数字按大小赋值成1~cnt，1对应的赋值成cnt+1~n，注意代码写法。
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)
print(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 = 2e5 + 5;
int t, n, a[N];
std::string s;
struct node {
int id, neww;
} c[N];
struct node1 {
int id, neww, pre;
} e[N];
struct node2 {
int id, neww, pre;
} q[N];
bool cmp(node a, node b) {
if (a.id < b.id)
return true;
else
return false;
}
bool cmp1(node1 a, node1 b) {
if (a.pre < b.pre)
return true;
else
return false;
}
bool cmp2(node2 a, node2 b) {
if (a.pre < b.pre)
return true;
else
return false;
}
int main() {
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
std::cin >> t;
while (t--) {
std::cin >> n;
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
std::cin >> s;
int len = s.length();
int cnt = 0, tot = 0, tt = 0;
for (int i = 0; i < len; i++) {
if (s[i] == '0') {
e[++cnt].id = i;
e[cnt].pre = a[i];
} else {
q[++tot].id = i;
q[tot].pre = a[i];
}
}
if (cnt == 0 || cnt == n) {
for (int i = 0; i < n; i++) {
std::cout << a[i] << " \n"[i == n - 1];
}
continue;
}
std::sort(e + 1, e + 1 + cnt, cmp1);
std::sort(q + 1, q + 1 + tot, cmp2);
for (int i = 1; i <= cnt; i++) {
e[i].neww = i;
c[++tt].id = e[i].id;
c[tt].neww = e[i].neww;
}
for (int i = 1; i <= tot; i++) {
q[i].neww = i + cnt;
c[++tt].id = q[i].id;
c[tt].neww = q[i].neww;
}
std::sort(c + 1, c + 1 + tt, cmp);
for (int i = 1; i <= tt; i++) {
std::cout << c[i].neww << " \n"[i == tt];
}
}
return 0;
}?C. Set or Decrease
给出一个数组和一个数字k，问能够操作的最少次数使数组所有元素和小于等于k。操作是指：1、选择一个数，将它减小1；2、选择两个数，将其中一个数值赋值给另一个。
思路：若是原数组所有元素和已经小于k，则无需任何操作；若大于k，首先最高效的的方法是令较大值等于较小值，所以要先排序，所以需要进行的操作就是对最小值进行p次1操作，对倒数q个数进行q次2操作，令它们等于改变后的最小值，我们可以先固定q的次数，寻找最小的p操作，从而寻找最小的p+q的值。 参考
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)
print(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;
ll t, n, a[N];
ll k;
int main() {
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> t;
while (t--) {
std::cin >> n >> k;
ll sum = 0;
for (ll i = 1; i <= n; i++) {
std::cin >> a[i];
sum += a[i];
}
if (sum <= k) {
std::cout << 0 << '\n';
continue;
}
std::sort(a + 1, a + 1 + n);
ll ans = sum - k, q = 1;
sum -= a[1];
for (ll i = n; i >= 2; i--) {
q++;
sum -= a[i];
ll p;
if (k - sum >= 0)//若小于k，若要达到正好的减少sum-k，对最小值需要增加，
p = (k - sum) / q;//但是显然不需要，所以有后面(1)处的操作
else
p = (k - sum - q + 1) / q;//若仍大于k，则需要对第一个数进行若干次减小操作
if (p > a[1])//(1)
p = a[1];
ans = std::min(ans, (a[1] - p) + q - 1);
}
std::cout << ans << '\n';
}
return 0;
}
若有错误请指教orzorz