A Remove Smallest
$$\color{orange}普及-\color{black}模拟$$
题目让我们算这个数组是不是连续的（允许相等）数，如果是输出 YES 否则输出 NO 。
为了方便之后删减元素，我使用 vector 容器。
因为给的数组不是有序的，所以需要先排序，排序用 sort 就行了。
之后我们就可以从小到大俩俩比较（ $w_i$ 和 $w_{i-1}$ ），如果 $w_i+w_{i-1}$ 超过 $1$ ，那么就直接给一个 NO 就行了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
inline int absd (int x)
{
return x > 0 ? x : -x;
}
vector <int> a;
int main ()
{
int t, n;
scanf ("%d", &t);
while (t --)
{
a.clear();
scanf ("%d", &n);
for (int i = 1; i <= n; i ++)
{
int x;
scanf ("%d", &x);
a.push_back(x);
}
int f = 0;
sort (a.begin(), a.end());
for (int i = 1; i < a.size(); i ++)
{
if (a[i] - a[i - 1] > 1)
{
f = 1;
break;
}
}
printf (f ? "NO\n" : "YES\n");
}
return 0;
}int absd (int x); 是手动处理绝对值的函数。
B Gifts Fixing
$$\color{orange}普及-\color{black}暴力枚举$$
注 数据范围能告诉你算法 $1 \le n \le 50$
题目就是让我们去算至少需要几步能将所有的数降到最小值。
题目说一共有 $3$ 种操作：
- $a_i \gets a_i-1$
- $b_i \gets b_i-1$
- $a_i \gets a_i-1;b_i \gets b_i-1$
其实就是当前 $a_i$ 与 $b_i$ 那个减那个，如果一样多就都减。
我们声明一个类 Gifts 里面有 a,b 两个成员。
struct Gifts
{
int a, b;
};用 Gifts v[] 来存输入的数据，用 Gifts vmin 来存储最小值。
之后暴力循环 v 中的每一个元素，用 a 和 b 记录当前值减去最小值（即当前需要减少几次），a 和 b 的 $max$ 即为这次需要挪动的次数。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
using namespace std;
typedef long long ll;
struct Gifts
{
int a, b;
};
int main ()
{
int t, n;
scanf ("%d", &t);
while (t --)
{
scanf ("%d", &n);
Gifts v[55];
Gifts vmin;
vmin.a = vmin.b = INT_MAX;
for (int i = 1; i <= n; i ++)
{
scanf ("%d", &v[i].a);
vmin.a = min (vmin.a, v[i].a);
}
for (int i = 1; i <= n; i ++)
{
scanf ("%d", &v[i].b);
vmin.b = min (vmin.b, v[i].b);
}
ll ans = 0;
for (int i = 1; i <= n; i ++)
{
int a = v[i].a - vmin.a,
b = v[i].b - vmin.b;
ans = ans + max (a, b);
}
printf ("%lld\n", ans);
}
return 0;
}C Boats Competition
$$\color{orange}普及/提高-\color{black}暴力枚举/二分答案$$
题目给我们一个数组 $w$ ，让我们在这个数组中求出在这 $n$ 个数的数列 $w$ 中两两相加，一共有多少组相等的。
我们枚举所有组的重量和 $i$ ( $i=w_x+w_y;2 \le i \le n \times 2$ )，在里面进行$二分答案$，二分这些重量里面那些可能组队（下标）。
- 如果左面的重量加上右面的重量大于总重量（ $w_l+w_r>i$ ），那么就扔掉右面的那个
- 如果反过来（ $w_l+w_r<i$ ），那么就扔掉左面的那个
- 如果正好（ $w_l+w_r=i$ ），那么就记录一个ans并扔掉左面的和右面的
为了保证上面的成立，必须先排序。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <algorithm>
using namespace std;
int n, w[55], c[55];
int main ()
{
int t;
scanf ("%d", &t);
while (t --)
{
scanf ("%d", &n);
for (int i = 1; i <= n; i ++)
{
scanf ("%d", &w[i]);
}
sort (w + 1, w + n + 1);
int ans = 0;
for (int i = 2; i <= n * 2; i ++)
{
int l = 1, r = n, tans = 0;
while (l < r)
{
if (w[l] + w[r] > i)
{
r --;
}
else if (w[l] + w[r] < i)
{
l ++;
}
else
{
tans ++;
r --, l ++;
}
}
ans = max (ans, tans);
}
printf ("%d\n", ans);
}
return 0;
}注 等级划分引自洛谷
- 分类： 题解 Codeforces
- 标签： Codeforces CF题解
- 浏览： 69