题目1
题目链接
题目大意：
给出一个数组长度为n，每次可以选择若干个数字，将其数字+1；
问最少需要操作几次，才能让整个数组内的元素值相等。
输入：
第一行，样例数𝑡 (1≤𝑡≤1e4)
每个样例两行，第一行整数𝑛 (1≤𝑛≤50)
第二行𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)
输出：
每个样例一行，输出最小的操作次数。
Examples
input
3
6
3 4 2 4 1 2
3
1000 1002 998
2
12 11
output
3
4
1
题目解析：
由贪心的思想，由最大值减去最小值就能得到最多需要操作次数k；
因为其他数字和最大值的差距，不会比这个值更大，肯定可以在k次操作内完成。
class Solution {
static const int N = 200010;
string str;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int valMin = a[0], valMax = a[0];
for (int i = 1; i < n; ++i) {
valMin = min(valMin, a[i]);
valMax = max(valMax, a[i]);
}
printf("%d\n", valMax - valMin);
}
}
}
ac;
题目2
题目链接
题目大意：
给出三个正整数a、b、c，现在可以对三个整数中的一个乘以正整数m；
这个操作只能执行一次，要求是最后三个成为等差数列。
比如说原来三个整数是10、5、30，那么可以将第二个乘以4，那么三个整数变为10、20、30，可以形成等差数列。
输入：
第一行样例数𝑡 (1≤𝑡≤1e4)
每个样例一行，包括整数𝑎, 𝑏, 𝑐 (1≤𝑎,𝑏,𝑐≤1e8).
输出：
如果有解，输出YES；如果无解，输出NO；
Examples
input
11
10 5 30
30 5 10
1 2 3
1 6 3
2 6 3
1 1 1
1 1 2
1 1 3
1 100000000 1
2 1 1
1 2 2
output
YES
YES
YES
YES
NO
YES
NO
YES
YES
NO
YES
题目解析：
最终想要形成的是等差数列，即是a-b=b-c；
由此可以推出来：
new_a=2b-c;
new_b=(a+c)/2;
new_c=2b-a;
那么就只要看最终new_a、new_b、new_c是不是原来的a、b、c的整数倍即可。
trick：
需要注意，由于m是正整数，所以new_a必须大于等于a才行。
class Solution {
static const int N = 200010;
string str;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int a, b, c;
cin >> a >> b >> c;
int ok = 0;
int new_a = 2 * b - c, new_b = (a + c) / 2, new_c = 2 * b - a;
if (new_a >= a && new_a % a == 0) {
ok = 1;
}
if (new_b >= b && new_b * 2 == (a + c) && (new_b % b == 0)) {
ok = 1;
}
if (new_c >= c && new_c % c == 0) {
ok = 1;
}
cout << (ok ? "YES" : "NO") << endl;
}
}
}
ac;
题目3
题目链接
题目大意：
给出n个正整数的数组a，现在每次可以对数组的一个元素操作：a[i]=a[i]除以2，向下取整；
问经过若干次操作之后，能否将数组变成1到n的排列，即数组是由整数1到n组成。
输入：
第一行样例数𝑡 (1≤𝑡≤1e4)
每个样例两行，第一行整数𝑛 (1≤𝑛≤50)
第二行n个整数 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e9)
输出：
如果有解，输出YES；如果无解，输出NO；
Examples
input
6
4
1 8 25 2
2
1 1
9
9 8 3 4 2 7 1 5 6
3
8 2 1
4
24 7 16 7
5
22 6 22 4 22
output
YES
NO
YES
NO
NO
YES
题目解析：
由贪心的思想可以知道，如果给出的整数a中存在1到n的整数，应该优先使用这些整数；
接着从剩下的整数中，不断挑选整数进行除2操作，如果遇到没有出现过的整数，则停止除2操作；
因为即使存在另外整数除以2会得到相同值的整数，在得到相同值的时候，他们已经是等价的整数了。
class Solution {
static const int N = 10010;
string str;
int a[N];
int cnt[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
cnt[i + 1] = 0;
}
int ok = 1;
for (int i = 0; i < n; ++i) {
while (a[i]) {
if (a[i] <= n && cnt[a[i]] == 0) {
cnt[a[i]] = 1;
break;;
}
a[i] /= 2;
}
if (!a[i]) {
ok = 0;
}
}
cout << (ok ? "YES" : "NO") << endl;
}
}
}
ac;
题目4
题目链接
题目大意：
小明在玩游戏，游戏中有n个怪兽站成一排，每个怪兽的血量为a[i];
小明可以释放技能，每次技能可以伤害其中1个怪兽2点血，以及左边或者右边相邻1点血；
比如说3个怪兽血量为[1,3,1]，则小明可以对中间怪兽释放两次技能，则可以把所有怪兽的血量清零；（怪兽血量为0仍然可以释放技能）
现在只需要把其中2个怪兽的血量清理，问最少需要放几次技能；
输入：
第一行，整数n (2≤𝑛≤2⋅1e5)
第二行，n个整数𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤1e6）
输出：
最少需要的技能次数；
Examples
input
5
20 10 30 10 20
output
10
题目解析：
这个题目用dp来解决，dp[i][0]表示前i怪兽打死1个的最小次数，dp[i][1]表示前i个怪兽打死2个的最小次数；
对于第i个怪物，有打死和不打死两种可能，不打死的话直接dp[i-1]转移，打死的话有多种可能：单独打死，和i-1一起打死，或者和i-2一起打死；
根据上面两种情况，得到两个状态的转移方程，即可解决问题，复杂度O(N)；
但是这个题目不需要动态规划，同样可以解决：
打怪兽只有两种可能，分开打死和一起打死，分开打死取数组最小2个元素即可，一起打死有下面两种可能：
1、两个怪兽是相邻的，可以假设血量为x和y（x<y），先只考虑对y放技能的情况，算出打死两个怪物的最少次数，然后考虑有多少个1/2的伤害可以替换为2/1；
2、两个怪兽是不相邻的，那么必然是打击中间的怪兽，掉两边的血；当有一个怪物死亡后，就可以瞄准剩下的怪物；（解决血量为[1,10,3]这样的情况）
复杂度同样为O(N)，并且不要考虑状态转移，实现更加简单；
class Solution {
static const int N = 201010;
int a[N], dp[N][2];
int check(int x, int y) {
int maxItem = max(x, y);
int minItem = min(x, y);
int cnt = 0;
if (minItem * 2 <= maxItem) {
cnt = (maxItem + 1) / 2;
}
else {
cnt = minItem - (minItem * 2 - maxItem) / 3;
}
return cnt;
}
public:
void solve() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int ans = 0xfffffff;
for (int i = 1; i < n; ++i) {
ans = min(ans, check(a[i], a[i - 1]));
if (i >= 2) {
ans = min(ans, min(a[i], a[i - 2]) + (a[i] + a[i - 2] - min(a[i], a[i - 2]) * 2 + 1) / 2);
}
}
sort(a, a + n);
ans = min(ans, (a[0] + 1) / 2 + (a[1] + 1) / 2);
cout << ans << endl;
}
}
ac;
题目5
题目链接
题目大意：
给出一个n x m的矩阵，由' . '和' * '组成；
现在想把矩阵内的星号全部调整到前面，比如说：
.*.
.**
.**
调整为
**.
**.
*..
先填充第1列，然后再填充第2列，以此类推，填充顺序为从上到下；
每次移动可以选择一个' * '移动到任意为' . '的位置；
现在有q次操作，每次会输入2个位置x和y，会把对应位置的元素修改为另外一个符号；
现在想知道每次操作之后，最少需要的移动次数；（每次操作的结果保留在矩阵中）
输入：
第一行，整数 𝑛, 𝑚 and 𝑞 (1≤𝑛,𝑚≤1000;1≤𝑞≤2⋅1e5)
接下q行，每行2个整数 𝑥𝑖 and 𝑦𝑖 (1≤𝑥𝑖≤𝑛;1≤𝑦𝑖≤𝑚)
输出：
输出q行，每行是操作后的最少移动次数；
Examples
input
4 4 8
..**
.*..
*...
...*
1 3
2 3
3 1
2 3
3 4
4 3
2 3
2 2
output
3
4
4
3
4
5
5
5
题目解析：
按照题目的要求，假设矩阵中有sum个星号，容易知道最终排成的元素会集中在j=(sum-1)/n列和i=(sum-1)%m行中；
并且我们得到一个快速计算移动次数的方法，假如前j列，前i行中一共有ans个星号，那么最少移动次数就是sum-ans；
容易知道q次操作中，每次操作之后影响str[x][y]这个位置，并且会导致sum变化，从而导致ans变化；
但是由于每次操作只能修改1个字符，我们只需判断下sum变化之前，最后一个位置是否为星号，就可以快速计算得到ans；
这样每次操作之后，计算sum和ans的复杂度只需要O(1)；
注意，每次操作之后，有两种可能会影响ans：
1、操作的字符就在最终排列的结果里面；
2、影响sum之后，sum关联到的对应的最后一个位置；
class Solution {
static const int N = 1010;
vector<string> str;
public:
void solve() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < n; ++i) {
string tmp;
cin >> tmp;
str.push_back(tmp);
}
int sum = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (str[i][j] == '*') {
++sum;
}
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (j * n + i < sum) {
if (str[i][j] == '*') {
++ans;
}
}
else {
break;
}
}
}
while (q--) {
int x, y;
cin >> x >> y;
--x;
--y;
if (str[x][y] == '*') {
str[x][y] = '.';
if (y * n + x < sum) {
--ans;
}
int j = (sum - 1) / n, i = (sum - 1) % n;
if ((i != x || j != y) && str[i][j] == '*') {
--ans;
}
--sum;
}
else {
str[x][y] = '*';
++sum;
if (y * n + x < sum) {
++ans;
}
int j = (sum - 1) / n, i = (sum - 1) % n;
if ((i != x || j != y) && str[i][j] == '*') {
++ans;
}
}
cout << sum - ans << endl;
}
}
}
ac;
网友评论