笔试专题（十六）

相差不超过k的最多数

题目链接

题解

1. 排序 + 滑动窗口
2. 为什么使用滑动窗口？
因为max-min <= k，求这个区间内的数最多，不定长的滑动窗口，可能中间的数最多，两边的数最多，所以让区间移动
3. 为何滑动窗口合法？
出窗口的时候我们是不确定left指针是否符合窗口，可能让left多次出窗口，第一个窗口中间的数依旧合法，因为一个大的数减一个小的数合法，依旧是这个大的数减比原先更大的数肯定也是合法的，所以不需要回退right指针，因此用滑动窗口

代码

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

const int N = 2e5 + 10;
int a[N];

int main()
{
    int n,k;
    cin >> n >> k;
    for(int i = 0;i < n;i++) cin >> a[i];

    int l = 0,r = 0;
    int ret = 0;
    sort(a,a+n);
    // 为什么使用滑动窗口,让最小值和最大值 <= k,区间就是满足要求的
    // 中间可能有奇怪的区间满足最大的区间,二两边的数不满足,让区间去移动,找最大的区间
    while(r < n)
    {
        while(a[r] - a[l] > k)
        {
            l++;
        } 
        ret = max(ret,r - l + 1);
        r++;
    }

    cout << ret << '\n';

    return 0;
}

最长公共子序列（一）

题目链接

题解

1. 动态规划
2. 状态表示：s1在[0,i]区间内以及s2[0,j]区间内，所有的子序列里面，最长公共子序列的长度
3. 状态转移方程：
如果最后一个位置s1[i] = s2[j]，那么就是前面的子序列加上最后一个位置的长度
如果最后一个位置s1[i] != s2[j]，那么可能是s1的[0,i-1]和s2的[0,j]中的最长公共子序列和s1的[0,i]和s2的[0,j-1]的最长公共子序列中的最大值

代码

class Solution 
{
public:
    int LCS(string s1, string s2) 
    {
        int m = s1.size();
        int n = s2.size();

        vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i = 1;i <= m;i++)
        {
            for(int j = 1;j <= n;j++)
            {
                if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
            }
        }

        return dp[m][n];
    }
};

小红的口罩

题目链接

题解

1. 贪心 + 小根堆
2. 每次选择最小的不舒适度，可以让让不舒适度缓慢增长，不超过k，可以让天数尽可能的大

代码

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

const int N = 1e5 + 10;
int a[N];

int main()
{
    // 小根堆
    priority_queue<int,vector<int>,greater<int>> pq;
    int n,k;
    cin >> n >> k;
    
    for(int i = 0;i < n;i++)
    {
        cin >> a[i];
        pq.push(a[i]);
    }
    
    int day = 0;
    while(k)
    {
        int t = pq.top();
        if(k - t >= 0)
        {
            k -= t;
            day++;
            pq.pop();
            t *= 2;
            pq.push(t);
        }
        else break;
    }
    
    cout << day << '\n';
    
    return 0;
}

春游

题目链接

题解

1. 贪心 + 分情况讨论

代码

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

typedef long long LL;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        LL n,a,b;
        cin >> n >> a >> b;
        
        LL ans = 0;
        if(n <= 2) 
        {
            if(a < b) cout << a << '\n';
            else cout << b << '\n';
            continue;
        }
        // 双人船
        if(3*a < 2*b)
        {
            int k = n / 2;
            ans += k * a;
            if(n % 2 == 1)
            {
                ans += min(min(a,b),(b-a));
            }
        }
        else if(3*a > 2*b)
        {
            // 三人船
            int k = n / 3;
            ans += k * b;
            if(n % 3 == 1)
            {
                ans += min(2*a-b,min(a,b));
            }
            else if(n % 3 == 2)
            {
                ans += min((3*a-b),min(a,b));
            }
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}