前言

题目难度适中，要争取AK，但是题目还是有一些灵活的，要分析情况题目的性质，套路性不是特别强。

第一题

小红有一个长度为n的01字符串，小红想知道最长的美丽连续子串是什么，输出它的长度。如果一个字符串的长度是偶数，且前一半全是0且后一半全是1或者前一半全是1且后一半全是0，那么这个字符串就是美丽串。

如0011，111000都是美丽串。

输入描述：

一行一个长度为n的01字符串。

输出描述：

输出一个整数表示答案。

示例1：

// 输入：
000001111011011

// 输出：
8

思路：

思维：找连续的0和1的个数，取相邻两个数目的最小值，再和ans取最大值即可

#include <iostream>
#include <string> 
using namespace std;

int main() {
    string s; cin >> s;
    int n = s.size(), ans = 0, prev = 0;
    for (int i = 0; i < n; ++i) {
        int j = i;
        while (j < n && s[j] == s[i]) ++j;
        int cur = min(prev, j - i);
        ans = max(ans, cur);
        prev = j - i;
        i = j - 1;
    }
    cout << ans << endl;
}

第二题

坐标轴上有n个人,位置分别是a1,a2,... ,an，有n个物资,位置分别是b1,b2,...bn,每个人可以拿走一个物资,每个物资只能被一个人拿走,然后走到终点p,每个人走一步需要花费1的时间,每个人拿走物资的时间为0，问最终每个物资都运送到终点时,每个人所花费时间总和的最小值。

输入描述：

一行两个整数n,p,表示人数和终点位置。一行n个整数a1,a2,..,an,表示每个人的位置。一行n个整数b1,b2,...,bn,表示每个物资的位置。

输出描述：

会出个整数，表示最短时间。

示例1：

// 输入：
3 3
1 4 3
2 5 6

// 输出：
11

// 说明
第一个人拿第一个物品花费时间1,走到终点花费时间1。
第二个人拿第三个物品花费时间2,走到终点花费时间3
第三个人拿第二个物品花费时间2,走到终点花费时间2。

思路：

贪心：可以看到位置的有序性并不影响最后的结果，因此可以先排序；那么最左边的人负责最左边的物品搬运，以此类推，肯定是最优的，最后累加距离即可；

#include <iostream>
#include <vector> 
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    {
        int n, p; cin >> n >> p;
        vector<int> a(n), b(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < n; ++i) cin >> b[i];
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        ll ans = 0;
        for (int i =0; i<n; ++i){
            ans +=abs(a[i]- b[i])+ abs (b[i]- p);
        }
        cout << ans;
    }
    return 0;
}

第三题

小红是一名科学家,她正在研究一种植物的叶子。这种植物的叶子有两个特征:颜色和形状。小红一共有n片叶子需要研究,她按照顺序依次摘取。然而,小红的研究假设是,研究一片叶子时,如果发现曾经已经研究过相同颜色和形状的叶子,那么本次研究的知识减半(向下取整)。现在问题是,小红可以自由排序,选择研究的顺序,最多可以获得多少知识。

输入描述：

第一行一个正整数n,表示叶子的数量。

第二行n个正整数a1, a2,...,an，表示每片叶子的颜色。

第三行行n个正整数b1,b2,...,bn,表示每片叶子的形状。

第四行行n个正整数c1,c2…,cn,表示第一次研究可以获得知识,如果之前见过相同颜色和形状的叶子,则获得的知识是ci/2(向下取整)。

输出描述：

一个整数,表示最多能获得的知识。

示例1：

// 输入：
4
1 2 2 2
1 2 3 2
2 3 4 5

// 输出：
12

// 说明：
按照1，4，3，2的研究顺序，获得知识2 + 5 + 4 +（3/2）= 12

思路：

哈希表：比较简单的题目，直接根据ai和bi建立哈希，对每一个key生成一个数组，存放ci，然后直接按照题目要求累加即可。

#include <iostream>
#include <vector> 
#include <algorithm>
#include <unordered_map>
using namespace std;
using ll = long long;

int main() {
    {
        int n; cin >>n;
        vector<int> color(n), shape(n), a(n);
        for (int i = 0; i < n; ++i) cin >> color[i];
        for (int i = 0; i < n; ++i) cin >> shape[i];
        for (int i = 0; i < n; ++i) cin >> a[i];
        ll ans = 0;
        unordered_map<ll, vector<int>> mp;
        for (int i=0; i<n; ++i){
            ll key = (ll)color[i]*(1e9 +1) + shape[i];
            mp[key].push_back(a[i]);
        }
        for (auto& [k, v]: mp) {
            sort(v.begin(), v.end(), greater());
            ll cur = v[0];
            for (int i = 1; i < v.size(); ++i) cur = v[i] / 2;
            ans += cur;
        }
        cout << ans;
    }
    return 0;
}

第四题

小红准备卖n个西瓜,已知每个西瓜的品质为ai。小红可以设置一个品质标准品质x，不小于x的西瓜为优质品。小红希望设置完品质标准x后,当顾客从左到右依次买瓜时，每个人买到优质品的概率都不小于P(顾客不知道哪个瓜是优质品,只知道剩下的瓜数量以及剩下的优质品数量)。小红想知道,x的最大值是多少?

输入描述：

第一行输入一个正整数n和一个正实数p,含义如题意所述。

第二行输入n个正整数ai,分别代表每个瓜的品质。

输出描述：

一个正整数,代表x的最大值。

示例1：

// 输入
4 0.5
5 3 9 6

// 输出：
6

// 说明：
当优质品标准设置为6时,第三个和第四个瓜是优质品：
第一个顾客买瓜时,买到优质品的概率是0.5。
第二个顾客买瓜时,买到优质品的概率是0.6666666。
第三个顾客买瓜时,买到优质品的概率是1。
第四个顾客买瓜时,买到优质品的概率是1。
可以证明,6为品质标准设置的最大值。

思路：

二分：其实只看题目并没有清楚具体含义，通过示例可以看出，顾客从左往右买瓜时，是按照次序买的，即第一个人只能买第一个瓜，那么就比较直观了；可以使用二分，枚举品质标准的设置值mid，再计算当品质标准为x时，是否满足买到优质品的概率不低于p；

#include <iostream>
#include <vector> 
#include <algorithm>
#include <unordered_map>
using namespace std;
using ll = long long;

int main() {
    {
        int n; double p; cin >> n >> p;
        vector<int>a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        int l = 1, r = 1e9;
        while (l <= r) {
            int mid = (l + r) / 2;
            bool ok = true;
            int good = 0;
            for (int i = n - 1;i >= 0 && ok; --i) {
                good += a[i] >= mid;
                double cur = good * 1.0 / (n - i);
                if (cur < p) ok = false;
            }
            if (ok)l = mid + l;
            else r = mid - l;
        }
        cout << l - 1;

    }
    return 0;
}