程序员进阶之算法练习（三十九）Codeforces

正文

1.Drinks Choosing

题目链接 题目大意： 有n个学生，每个学生都有自己喜欢的饮料类型，用整数?1,?2,…,?? (1≤??≤?)表示，一共有k种饮料的类型。 现在老师要采购饮料，饮料是两瓶装； 所以老师打算采购(n/2)个单位，保证每个学生至少有一瓶。（n/2向上取整，如果5个人，老师会买3个单位） 老师希望尽可能多的学生能喝到喜欢的饮料类型，问最多能有几个学生喝到自己喜欢的饮料？

输入： 第一行，? and ? (1≤?,?≤1000) 接下来n行，分别表示 ?1,?2,…,?? (1≤??≤?)

输出： 能够喝到喜欢饮料的学生人数；

Examples input 5 3 1 3 1 1 2 output 4

题目解析： 兴趣相同的，两两成对拿出来，凑成一个单位；(ans += 2) 剩下的所有人(n - ans)，每个人的兴趣都不相同，任意两两凑对一个单位；(n-ans+1)/2

    int n, k;
    cin >> n >> k;
    int a[1001] = {0}, ans = 0;
    for (int i = 0; i < n; ++i) {
        int t;
        cin >> t;
        ++a[t];
        if (a[t] % 2 == 0) {
            ans += 2;
        }
    }
    ans += (n - ans + 1) / 2;
    cout << ans << endl;

2.Sport Mafia

题目链接 题目大意： 小明有个糖果盒子，起始的时候是空的。 小明会进行n次操作，每次可以选择： 1、吃掉盒子里的一个糖果；（如果里面有糖果的话） 2、放进去x个糖果，之后x=x+1；（比如这次是放5个，下次就是放6个） 最后盒子里会剩下k个糖果；

例如下面的9个操作： put 1 candy, put 2 candies, eat a candy, eat a candy, put 3 candies, eat a candy, put 4 candies, eat a candy, put 5 candies.

最终会剩下11个糖果。（1+2−1−1+3−1+4−1+5=11）

现在给出操作次数n，还有最终剩下的k个糖果，问小明会吃掉几个糖果。

输入： 第一行，? and ? (1≤?≤10^9; 0≤?≤10^9)

输出： 小明吃掉的糖果数；（题目保证数据是有解的）

Examples input 5 3 1 3 1 1 2 output 4

题目解析： 由题目知道，吃掉的糖果是1、2、3、4、、、，那么假设吃掉的是1~t的糖果。 那么剩下的(n-t)次糖果，肯定是吃糖果的操作。 如果题目有解，那么就有： 总共的放进去糖果数 = 吃糖果数 + 剩下糖果数； 即是：(1+t)*t/2 = (n-t) + k；

可以从1开始遍历t，最多重复sqrt(10^9)次就会有解，复杂度可以接受。

    int n, k;
    cin >> n >> k;
    for (int i = 1; i < 100000; ++i) {
        lld sum = (1ll + i) * i / 2;
        if (sum == (k + (n - i))) {
            cout << sum - k << endl;
            return 0;
        }
    }

3.Basketball Exercise

题目链接 题目大意： 篮球教练有2 * n个学生，排成两行，每行有n个人；

每个学生都有一个高度h；(1≤h≤10e9)

现在教练需要选择若干个学生去参加篮球比赛，他决定从左到右选择学生，并且：

1、每列只选择一个学生；

2、不连续选择两个同一行的学生，如果这次选择了第一行的学生，则下次必然选择第二行的学生；

问选择出来的学生高度和最大值是多少；

输入： 第一行，? (1≤?≤10e5) 第二行，n个整数h，表示第一行学生高度 (1≤ℎ≤10e9) 第三行，n个整数h，表示第二行学生高度 (1≤ℎ≤10e9)

输出： 选择出来的学生高度总和最大值；

Examples input 5 9 3 5 7 3 5 8 1 4 5 output 29

图中灰色为选中学生

input 3 1 2 9 10 1 1 output 19

图中灰色为选中学生

题目解析： 两个数组，从左到右遍历选择数字，每个index只能选择一个数字，并且两个数组要交替选择。

对于每个数字，只有两种选择：选中或者不选中； 对于每个index，则有三种状态：选择数组a的元素（状态1）、选择数组b的元素（状态2）、都不选择（状态0）； 那么有dp[N][i]： dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]); dp[i][1] = max(dp[i-1][2], dp[i-1][0]) + a[i]; dp[i][2] = max(dp[i-1][1], dp[i-1][0]) + b[i];

然后选择dp[N][i]中的最大值即可。

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    
    lld ans = max(a[0], b[0]);
    dp[0][0] = 0;
    dp[0][1] = a[0];
    dp[0][2] = b[0];
    
    for (int i = 1; i < n; ++i) {
        dp[i][0] = max(max(dp[i-1][0], dp[i-1][1]), dp[i-1][2]);
        dp[i][1] = max(dp[i-1][2], dp[i-1][0]) + a[i];
        dp[i][2] = max(dp[i-1][1], dp[i-1][0]) + b[i];
        for (int j = 0; j < 3; ++j) {
            ans = max(ans, dp[i][j]);
        }
    }
    
    cout << ans << endl;

4.Letters Shop

题目链接 题目大意： 有一个小写字母组成的字符串s，长度为n； 有m个人，每个人有一个名字，假如是t[i]； 现在小明想知道，对于每个人，至少需要s的前面多少个字符，才能组成他的名字；

假如 ? ="arrayhead"，?[?]="arya"，那么需要前面5个字符array，才能够组成arya的名字； 假如 ? ="arrayhead"，?[?]="areahydra"，那么需要前面9个字符arrayhead，才能组成areahydra的名字；

输入： 第一行，整数?，表示字符串长度 (1≤?≤2⋅10^5) 第二行，字符串s； 第三行，整数m，表示m个人； (1≤?≤5⋅10^4) 接下来m行，每行有一个字符串t[i]； (1≤|?[?]|≤2⋅10^5) 题目保证每个人的名字，都可以由字符串s组成，并且m个人的名字总长度不会超过2⋅10^5。

输出： m行，每行有一个数字，表示需要的最少字符数量。

题目解析： 先不考虑复杂度，直接的做法是将每个人的名字拿出来匹配，一共匹配m次； 怎么匹配比较方便？ 把名字统计下，得到b[26]，表示26个字符的数量； 然后遍历整个字符串，直到26个字母的数量都满足； 复杂度是O(N)，总的复杂度是O(NM)；

这个复杂度太高，需要优化。 容易知道，如果前i个字符满足要求，则前i+1个字符也满足要求，那么就可以二分。 同时为了避免多次计算，可以直接换成a[i][j]表示前i个字符，第j个字母的数量。

    int n;
    cin >> n;
    string str;
    cin >> str;
    a[0][str[0] - 'a'] = 1;
    
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < 26; ++j) {
            a[i][j] = a[i - 1][j];
        }
        ++a[i][str[i] - 'a'];
    }
    
    int m;
    cin >> m;
    while (m--) {
        string t;
        cin >> t;
        int cnt[26] = {0};
        for (int i = 0; i < t.length(); ++i) {
            ++cnt[t[i] - 'a'];
        }
        
        int l = 0, r = n - 1, ans = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            
            int ok = 1;
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] && a[mid][i] < cnt[i]) {
                    ok = 0;
                }
            }
            
            if (ok) {
                ans = mid;
                r = mid - 1;
            }
            else {
                l = mid + 1;
            }
        }
        
        cout << ans + 1 << endl;
    }

总结

题目1是贪心，也没有特别的trick； 题目2提供的解法是暴力去枚举，如果操作的次数比较多，比如说n=10e18，此时放入糖果的操作次数会比较多，此时可以使用二分查找；（判断条件是糖果有没有剩余） 题目3是动态规划，状态转移比较简单；样例的数据有点像LIS（最长上升子序列），一开始理解错题意，以为是要求选择出来的人是要身高递减，但是这个题目又不能按照LIS一样做到O(NlogN)； 题目4就是典型的二分题目。