美文网首页
程序员进阶之算法练习(七十)

程序员进阶之算法练习(七十)

作者: 落影loyinglin | 来源:发表于2022-12-15 22:05 被阅读0次

题目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;

相关文章

网友评论

      本文标题:程序员进阶之算法练习(七十)

      本文链接:https://www.haomeiwen.com/subject/hzmkxdtx.html