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

题目1

题目链接 题目大意： 有这样的一个字符串，如图：

现在光标停留在最左边的数字1处，我们可以进行以下的操作： 1、将当前光标所在位置的数字输出； 2、移动光标到相邻的数字，比如说从1移动到2，从2移动到3；（1的左边不能移动，0的右边不能移动）

现在想知道，输出特定的4个字符，最少需要几次操作。

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例一行，4个整数；

输出： 每个样例一行，输出最少的操作次数。

Examples input 10 1111 1236 1010 1920 9273 0000 7492 8543 0294 8361

output 4 9 31 27 28 13 25 16 33 24

题目解析： 输出数字的最小操作方法: 1、将光标移到指定位置； 2、展示当前数字；

题目的意思非常简单，但是如果直接通过if去实现，在计算0的位置时，会比较繁琐；（因为数字0在最右边，破坏了字符和数字的对应关系） 这里有个实现的小技巧，我们将数字0看成10，那么整个数字序列就是从小到大。 这样在计算操作1的时候，就能通过数字相减直接得到结果。

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            char s[10];
            cin >> s;
            int cur = 1, ans = 4;
            for (int i = 0; i < 4; ++i) {
                int idx = s[i] - '0';
                if (idx == 0) idx += 10;
                ans += abs(cur - idx);
                cur = idx;
            }
            cout << ans << endl;
        }
    }
}
ac;

题目2

题目链接 题目大意： 给出一个长度为n的字符串s，现在需要移除字符串中的k个字符，剩下的字符可以随意排列； 问，剩下的字符能否组成一个回文串？

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例2行 第一行，𝑛 and 𝑘 (0≤𝑘<𝑛≤1e5) 第二行，字符串s；（小写字母组成）

输出： 每个样例一行，如果有解则输出YES；如果无解则输出NO；

Examples input 14 1 0 a 2 0 ab 2 1 ba 3 1 abb 3 2 abc 6 2 bacacd 6 2 fagbza 6 2 zwaafa 7 2 taagaak 14 3 ttrraakkttoorr 5 3 debdb 5 4 ecadc 5 3 debca 5 3 abaac

output YES NO YES YES YES YES NO NO YES YES YES YES NO YES

题目解析： 最终的字符串可以任意调整顺序，那么重点在于每个字符的数量； 题目是要求构造回文串，如果某个字符数量是偶数，那么可以组成回文串；如果某个字符数量是奇数，那可能会导致无法构成回文串。 假设统计所有字符的数量，有x个偶数字符，有y个奇数字符；那么能构成回文串的条件就是y<=1；（如果只有1个奇数，可以把多出来这个字符放在回文串中间） 由于题目增加了一个限制，要去除k个字符，那么奇数字符就可以有更多（因为移除时优先移除奇数字符），所以最终条件是y<=1+k；

class Solution {
    static const int N = 201010;
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, k;
            string s;
            cin >> n >> k;
            cin >> s;
            vector<int> cnt(26);
            for (int i = 0; i < n; ++i) cnt[s[i] - 'a']++;
            int y = 0;
            for (int i = 0; i < 26; ++i) y += (cnt[i] % 2);
            if (y <= 1 + k) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
}
ac;

题目3

题目链接 题目大意： 有n个整数的数组a，再给出整数k； 现在可以进行任意次以下操作： 选择某个数组元素，将该元素+1；

现在要求数组最终的乘积，能够整除数字k，问最少需要操作多少次；

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例2行 第一行，𝑛 and 𝑘 (2≤𝑛≤1e5 , 2≤𝑘≤5 ) 第二行，n个整数𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤10).

输出： 每个样例一行，输出最小的操作次数。

Examples input 15 2 5 7 3 3 3 7 4 1 5 2 9 7 7 3 9 5 5 5 4 1 2 3 7 4 9 5 1 5 9 5 1 3 4 6 3 6 3 4 6 1 5 3 4 1 5 9 4 4 1 4 1 1 3 4 3 5 3 4 5 8 9 9 3 2 5 1 6 2 5 10 10 4 5 1 6 1 1 2 5 7 7 output 2 2 1 0 2 0 1 2 0 1 1 4 0 4 3

题目解析： 第一反应，是将k进行因数分解，然后将数字分配到对应因数，还要考虑一个数字对应多个因数的情况（比如说a1=25，可以对应到两个因数5）； 这样题目整体处理会比较麻烦。 考虑到k的数据范围很小，因数情况也只有4=2x2的可能，可以不使用这种方法来处理。

假如k=2时，如果数组a存在偶数，则ans=0，否则ans=1； 假如k=3时，判断每个数组元素与3的余数即可，如果有能整除，则ans=0，否则为ans=3-最大余数； 假如k=4时，按照2的因数来算，比如说4就算2个，如果数组中存在2个，那么ans=0；如果数组中存在1个，那么ans=1（因为必然还有一个奇数，这个奇数可以+1得到偶数）；如果数组中存在0个，那么ans=2（因为有两个数字，必定是2个奇数）；（同时也可以按照k=3的做法，计算下如果累加每个数字的情况，取较小者） 假如k=5时，可以按照k=3的做法来；

class Solution {
    static const int N = 201010;
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, k;
            cin >> n >> k;
            int ans = 0, cnt = 0;
            while (n--) {
                int tmp;
                cin >> tmp;
                if (tmp % k) ans = max(ans, tmp % k);
                else ans = k;
                while (tmp % 2 == 0) {
                    ++cnt;
                    tmp /= 2;
                }
            }
            if (k == 4) {
                if (cnt >= 2) cout << 0 << endl;
                else cout << min(k - ans, 2 - cnt) << endl;
            }
            else {
                cout << (k - ans) << endl;
            }
        }
    }
}
ac;

题目4

题目链接 题目大意： 有n个整数的数组𝑎1,𝑎2,…,𝑎𝑛 现在可以对数组进行多次下述操作： 选择数组中的某个整数𝑎𝑖，如果𝑎𝑖<0 则可以把𝑎𝑖替换为[𝑎𝑖,0]区间中的整数；如果𝑎𝑖>0，则可以把𝑎𝑖替换为 [0,𝑎𝑖] 区间中的整数.

现在想知道最少需要多少次操作，才能使得最终数组所有数字的乘积尽可能的小；

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤500) 每个样例2行 第一行，整数𝑛(1≤𝑛≤100) 第二行，n个整数𝑎1,𝑎2,…,𝑎𝑛(−1e9≤𝑎𝑖≤1e9).

输出： 每个样例第一行，输出需要的操作次数x； 接下来每个操作一行，输出参数i和x，表示将a[i]设置为x；

Examples input 4 1 155 4 2 8 -1 3 4 -1 0 -2 -5 4 -15 -75 -25 -30

output 1 1 0 0 0 1 3 0

题目解析： 题目的要求的是乘积尽可能小，如果数组当前乘积结果是正数，那么将任意一个数字变为0，结果就是最小值0； 如果当前乘积是数字0，那么不管如何修改，最终结果都是0； 如果当前乘积是数字负数，那么修改任何数字，都可能会让结果更大，而不是更小。

思路想清楚，代码就很简单了。

class Solution {
    static const int N = 201010;
    int a[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            int zero = 0, cnt = 0;
            for (int i = 0; i < n; ++i) cin >> a[i];
            for (int i = 0; i < n; ++i) {
                if (a[i] == 0) ++zero;
                else if (a[i] < 0) ++cnt;
            }
            if (cnt % 2 || zero) cout << 0 << endl;
            else cout << "1\n 1 0" << endl;
        }
    }
}
ac;

题目5

题目链接 题目大意： 有n个整数区间[𝑙1,𝑟1],[𝑙2,𝑟2],…,[𝑙𝑛,𝑟𝑛]，每个区间有一个系数 𝑐𝑖，每个区间的重量为𝑐𝑖⋅(𝑟𝑖−𝑙𝑖). 现在可以进行下列操作： 1、任意调换n个整数区间，左区间l的数字； 2、任意调换n个整数区间，右区间r的数字； 3、任意调换n个整数区间，系数c的数字； 要求调换完，每个区间 [𝑙𝑖, 𝑟𝑖] 都满足 𝑙𝑖 < 𝑟𝑖;

输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤10000) 每个样例有4行 第一行，整数 𝑛 (1≤𝑛≤2e5) 第二行，整数 𝑙1,𝑙2,…,𝑙𝑛(1≤𝑙𝑖≤2⋅1e5) 第三行，整数 𝑟1,𝑟2,…,𝑟𝑛 (𝑙𝑖<𝑟𝑖≤2⋅1e5) 第四行，整数𝑐1,𝑐2,…,𝑐𝑛 (1≤𝑐𝑖≤1e7 )

题目保证，{𝑙1,𝑙2,…,𝑙𝑛,𝑟1,𝑟2,…,𝑟𝑛}数字各不相同。

输出： 每个样例一行，输出调整后，所有区间的最小重量和。

Examples input 2 2 8 3 12 23 100 100 4 20 1 2 5 30 4 3 10 2 3 2 3

output 2400 42

题目解析： 题目允许对l、r、c进行任意调换，那么可以先对l、r、c进行从小到大排序，便于分析问题。 接下来做数据分析，先考虑n=2的情况 a1 a2 b1 b2 c1 c2 正常情况下 (b1-a1)c1 + (b2 - a2)c2 先考虑c1和c2的情况，假设b1-a1和b2-a2相等，那么调换c1和c2对于结果没有影响。 假设b1-a1<b2-a2呢？ 这次c1<c2就会导致更小的结果，应该把更大的数字放在前面。

延伸分析，假设有若干个区间长度，那么可以将区间长度从小到大排序，接着把c越大的匹配到越前面的结果。

接下来，就是怎么匹配出来若干个区间长度，并且保证结果符合要求。 首先还是从2个区间开始分析 a1 a2 b1 b2 我们知道最终两个区间的和，不管如何交换，必然是 (b1 - a1) + (b2 - a2)。 那在这种情况下，我们让其中一个区间尽可能小，另外一个区间必然会增大。

沿着这个贪心思路，我们只需要每次让右区间，去匹配到尽可能接近的左区间。 有一个简单实现方案，对于每一个左区间（从大到小开始），我们从大到小去遍历右区间，找出来一个最近的节点。 但是这样的复杂度是O(N x N)；

我们可以引入优先队列来简化操作，在选择右区间的时候，big队列表示前面选择过的节点队列，从大到小排列，这样就可以直接从big队列中找到之前遍历过的最大值； backup表示还没有被选择过的节点，从小到大排列，这样当big队列最大值都无法满足要求，就需要从backup中取数字。 这样整体的复杂度就可以降低到NlogN的级别。

class Solution {
    static const int N = 201010;
    priority_queue<int> big;
    priority_queue<int, vector<int>, greater<int> > backup;
    int a[N], b[N], c[N], diff[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            for (int i = 0; i < n; ++i) cin >> a[i];
            for (int i = 0; i < n; ++i) cin >> b[i];
            for (int i = 0; i < n; ++i) cin >> c[i];
            sort(a, a + n);
            sort(c, c + n);
            for (int i = 0; i < n; ++i) backup.push(b[i]);
            for (int i = n - 1; i >= 0; --i) {
                int cur = 0;
                if (!big.empty()) {
                    cur = big.top();
                }
                if (cur < a[i]) { // 当前big堆里不满足
                    while (cur < a[i]) {
                        cur = backup.top();
                        big.push(cur);
                        backup.pop();
                    }
                    big.pop();
                }
                else {
                    big.pop();
                    while (big.size() && big.top() > a[i]) {
                        backup.push(cur);
                        cur = big.top();
                        big.pop();
                    }
                }
                diff[i] = cur - a[i];
            }
            sort(diff, diff + n);
            lld ans = 0;
            for (int i = 0; i < n; ++i) ans += diff[i] * 1LL * c[n - 1 - i];
            cout << ans << endl;
        }
    }
}
ac;