程序员进阶之算法练习（七十）
题目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 2output
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;