旺崽的博客

要么天赋异禀，要么天道酬勤

0%

发表于 分类于 Valine：

题目链接

Problem Statement

We have a grid with N horizontal rows and N vertical columns.
Let (i,j) denote the square at the i-th row from the top and j-th column from the left. A character $c_{i,j}$ describes the color of (i,j).
B means the square is painted black; W means the square is painted white; ? means the square is not yet painted.

Takahashi will complete the black-and-white grid by painting each unpainted square black or white.
Let the zebraness of the grid be the number of pairs of a black square and a white square sharing a side.
Find the maximum possible zebraness of the grid that Takahashi can achieve.

Sample Input 1

1
2
3
2
BB
BW

Sample Output 1

1
2

Sample Input 2

1
2
3
4
3
BBB
BBB
W?W

Sample Output 2

1
4

Sample Input 3

1
2
3
4
5
6
5
?????
?????
?????
?????
?????

Sample Output 3

1
40

建图+网络流~
对一个为 n*n 的矩阵，显然最大值就是 2n(n-1)，那么这题就可以转化成一个最小割(或者最大流)，答案就是最大值减去最小割，建图如下：

  • 每一个点和四周的点连边，流量为 $1$
  • 对所有非 ? 的点，判断奇偶性连一条 inf 边到源点或者汇点

注意算法复杂度，EK 算法可能会超时，要用 Dicnic 算法，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
#define inf 0x3f3f3f3f

struct edge {
    int from, to;
    int cap;
    int flow;

    edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {
    }
};

vector<edge> edges;
vector<int> G[MAXN];
int vis[MAXN];
int d[MAXN];
int cur[MAXN];
int m;
int s, t;

void add(int from, int to, int cap) {
    edges.push_back(edge(from, to, cap, 0));
    edges.push_back(edge(to, from, 0, 0));
    int m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
}

bool bfs() {
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(s);
    d[s] = 1;
    vis[s] = 1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < G[x].size(); i++) {
            edge &e = edges[G[x][i]];
            if (!vis[e.to] && e.cap > e.flow) {
                vis[e.to] = 1;
                d[e.to] = d[x] + 1;
                q.push(e.to);
            }
        }

    }
    return vis[t];
}

int dfs(int x, int a) {
    if (x == t || a == 0)
        return a;
    int flow = 0, f;
    for (int &i = cur[x]; i < G[x].size(); i++) {
        edge &e = edges[G[x][i]];
        if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
            e.flow += f;
            edges[G[x][i] ^ 1].flow -= f;
            flow += f;
            a -= f;
            if (a == 0)
                break;
        }
    }
    return flow;
}

int dicnic() {
    int ans = 0;
    while (bfs()) {
        memset(cur, 0, sizeof(cur));
        ans += dfs(s, inf);
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<string> c(n);
    for (int i = 0; i < n; i++) cin >> c[i];
    s = n * n + 1, t = n * n + 2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x = i * n + j;
            if (c[i][j] == 'B') {
                if ((i + j) % 2) add(s, x, inf);
                else add(x, t, inf);
            } else if (c[i][j] == 'W') {
                if ((i + j) % 2) add(x, t, inf);
                else add(s, x, 10);
            }
            if (i < n - 1) {
                int y = (i + 1) * n + j;
                add(x, y, 1);
                add(y, x, 1);
            }
            if (j < n - 1) {
                int y = i * n + j + 1;
                add(x, y, 1);
                add(y, x, 1);
            }
        }
    }
    cout << 2 * n * (n - 1) - dicnic();
    return 0;
}

发表于 分类于 Valine：

题目链接

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组，则返回 0 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：nums = [8,2,4,7], limit = 4
输出：2 
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4. 
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4. 
因此，满足题意的最长子数组的长度为 2 。

示例 2：

1
2
3
输入：nums = [10,1,2,4,7,2], limit = 5
输出：4 
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。

示例 3：

1
2
输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3

双指针~
我们开设两个指针 $l,r$，先移动 $r$ 指针，并记录区间 $[l,r]$ 内的最大值 $mx$ 和最小值 $mn$，显然当 $mx-mn\leq limit$ 时，区间长度就是答案；当条件不满足时，我们只需要固定 $r$ 指针，移动 $l$ 指针即可，即必须缩短区间长度以满足题目所给条件，但是我们移动指针的过程中要同时改变最大最小值，显然光开两个变量是不够的，我提供了两种方法：

  • 开一个大根堆 $mx$ 和小根堆 $mn$，显然堆顶就是我们要找的最大最小值，维护两个堆即可
  • C++里面有一个强大的数据结构 $multiset$（同样是最容易被忽视的数据结构），这个数据结构自动排序且支持元素重复，显然 $multiset$ 的迭代器指向的开头和末尾就是我们要找的最大最小值

下面两段代码分别对应第一种和第二种方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestSubarray(vector<int> &nums, int limit) {
        int l = 0, r = 0, ans = 0;
        unordered_map<int, int> cnt;
        priority_queue<int, vector<int>, less<>> mx;
        priority_queue<int, vector<int>, greater<>> mn;
        while (r < nums.size()) {
            cnt[nums[r]]++;
            mx.emplace(nums[r]);
            mn.emplace(nums[r]);
            while (mx.top() - mn.top() > limit) {
                cnt[nums[l]]--;
                while (!cnt[mx.top()]) mx.pop();
                while (!cnt[mn.top()]) mn.pop();
                l++;
            }
            ans = max(ans, r - l + 1);
            r++;
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestSubarray(vector<int> &nums, int limit) {
        int l = 0, r = 0, ans = 0;
        multiset<int> temp;
        while (r < nums.size()) {
            temp.emplace(nums[r]);
            while (*temp.rbegin() - *temp.begin() > limit) {
                temp.erase(temp.find(nums[l++]));
            }
            ans = max(ans, r - l + 1);
            r++;
        }
        return ans;
    }
};

发表于 分类于 Valine：

题目链接

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

说明:

1
不允许旋转信封。

示例:

1
2
3
输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3 
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

非常经典的二维最长上升子序列，对一维的最长上升子序列，我们很熟悉，但是二维的就必须要排序，那么有下面两种排序方案：

  • 一维正序，二维正序
  • 一维正序，二维逆序

相信绝大部分人都会选择第一种排序方案，但是这样一来算法复杂度就会达到 $O(n^2)$(对每一个信封，必须遍历此信封之前的所有信封才能得到最优解)，为了降低时间复杂度，我们可以选择第二种排序方案：
即用一个数组装信封，先装入第一个信封，然后对之后的信封 $i$ 直接二分答案数组，判断里面是否有宽高都大于该信封的信封 $j$，如果没有，证明 $i$ 此时是宽高最大的信封，直接装入答案数组；若有，我们就可以用 $i$ 替换 $j$ 的位置以获得更长的俄罗斯套娃，最后信封数组的长度就是答案，算法复杂度 $O(nlogn)$，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    static bool cmp(vector<int> &a, vector<int> &b) {
        if (a[0] != b[0]) return a[0] < b[0];
        return a[1] > b[1];
    }

    int maxEnvelopes(vector<vector<int>> &envelopes) {
        if (envelopes.size() == 0) return 0;
        sort(envelopes.begin(), envelopes.end(), cmp);
        vector<int> temp;
        temp.push_back(envelopes[0][1]);
        int n = envelopes.size();
        for (int i = 1; i < n; i++) {
            auto it = lower_bound(temp.begin(), temp.end(), envelopes[i][1]);
            if (it == temp.end()) temp.push_back(envelopes[i][1]);
            else *it = envelopes[i][1];
        }
        return temp.size();
    }
};

发表于 分类于 Valine：

题目链接

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

示例 1：

1
2
3
4
5
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释： 
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

1
2
3
4
5
输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

双指针~
这题和 LeetCode 424 替换后的最长重复字符 方法一模一样，就是利用双指针的思想找最大区间，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestOnes(vector<int> &A, int K) {
        int l = 0, r = 0, n = A.size(), num0 = 0, num1 = 0, mx = 0;
        while (r < n) {
            A[r] ? num1++ : num0++;
            mx = max(mx, num1);
            if (r - l + 1 - mx > K) {
                A[l] ? num1-- : num0--;
                l++;
            }
            r++;
        }
        return r - l;
    }
};

发表于 分类于 Valine：

题目链接

在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。

返回所需的 K 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。

示例 1：

1
2
3
输入：A = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。

示例 2：

1
2
3
输入：A = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

示例 3：

1
2
3
4
5
6
输入：A = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]

差分~
这种一次连续改 $k$ 位的题就是很经典的差分，我们只需要从左往右扫，碰到 $0$ 就改成 $1$ 即可，注意因为是连续修改，所以要用差分，线段树肯定也行，但是要麻烦许多，做完这题的可以类比牛客寒假训练营的一道题：题目链接，也是利用差分的性质，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minKBitFlips(vector<int> &A, int K) {
        vector<int> diff(A.size() + 1, 0);
        int flag = 0, ans = 0;
        for (int i = 0; i < A.size(); i++) {
            flag += diff[i];
            if (flag % 2) A[i] ^= 1;
            if (i <= A.size() - K && !A[i]) {
                A[i] = 1;
                ans++;
                diff[i]++;
                diff[i + K]--;
                flag++;
            }
        }
        int sum = accumulate(A.begin(), A.end(), 0);
        if (sum != A.size()) return -1;
        return ans;
    }
};

发表于 分类于 Valine：

题目链接

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

1
2
3
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

1
2
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

1
2
输入：nums = [7,7,7,7,7,7,7]
输出：1

经典 DP，这里挂一个 $O(NlogN)$ 的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private:
    int dp[2505];
public:
    int bs(int s, int e, int key) {
        while (s <= e) {
            if (s == e) return s;
            int mid = (s + e) >> 1;
            if (dp[mid] < key) s = mid + 1;
            else e = mid;
        }
        return 0;
    }

    int lengthOfLIS(vector<int> &nums) {
        dp[0] = -1e9;
        int top = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > dp[top])
                dp[++top] = nums[i];
            else {
                int k = bs(1, top, nums[i]);
                dp[k] = nums[i];
            }
        }
        return top;
    }
};

发表于 分类于 Valine：

题目链接

Problem Statement

There are N kinds of materials. Material i has a magic power of Ai.

Takahashi, the magician, wants to make a potion by choosing one or more kinds from these materials and mixing them.

At the moment when he makes a potion by mixing k kinds of materials, the magic power of the potion is the sum of the materials used. Then, every second, its magic power increases by k. Note that the increase of the magic power is a discrete - not continuous - process.

Takahashi will mix materials just once, at time 0. What is the earliest time he can get a potion with a magic power of exactly X?

Under the constraints, it can be proved that it is possible to make a potion with a magic power of exactly X.

Sample Input 1

1
2
3 9999999999
3 6 8

Sample Output 1

1
4999999994

Sample Input 2

1
2
1 1000000000000000000
1

Sample Output 2

1
999999999999999999

动态规划，背包DP~

首先我们可以暴力选取材料的种类 $c$，$c\in[1,n]$，用 dp[i][j][k] 表示前 i 个数里选 j 个数且模数为 k 的最大值 sum，且 k=sum%c，则有如下的状态转移方程：

计算出最大值后对应 c 种材料所需时间即为 $t=\frac{x-dp[n][c][x\%c]}{c}$，AC 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n, x, ans = INT64_MAX, a[105], dp[105][105][105];

int main() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int t = 1; t <= n; t++) {
        memset(dp, 0x80, sizeof(dp));
        dp[0][0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= t; j++) {
                for (int k = 0; k < t; k++) {
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][(k - a[i] % t + t) % t] + a[i]);
                }
            }
        }
        if (dp[n][t][x % t] > 0) ans = min(ans, (x - dp[n][t][x % t]) / t);
    }
    cout << ans;
    return 0;
}

发表于 分类于 Valine：

题目链接

Problem Statement

A train goes back and forth between Town A and Town B. It departs Town A at time 0 and then repeats the following:

  • goes to Town B, taking X seconds;
  • stops at Town B for Y seconds;
  • goes to Town A, taking X seconds;
  • stops at Town A for Y seconds.

More formally, these intervals of time are half-open, that is, for each n=0,1,2,…:

  • at time t such that (2X+2Y)n≤t<(2X+2Y)n+X, the train is going to Town B;
  • at time t such that (2X+2Y)n+X≤t<(2X+2Y)n+X+Y, the train is stopping at Town B;
  • at time t such that (2X+2Y)n+X+Y≤t<(2X+2Y)n+2X+Y, the train is going to Town A;
  • at time t such that (2X+2Y)n+2X+Y≤t<(2X+2Y)(n+1), the train is stopping at Town A.

Takahashi is thinking of taking this train to depart Town
A at time 0 and getting off at Town B. After the departure, he will repeat the following:

  • be asleep for P seconds;
  • be awake for Q seconds.

Again, these intervals of time are half-open, that is, for each n=0,1,2,…:

  • at time t such that (P+Q)n≤t<(P+Q)n+P, Takahashi is asleep;
  • at time t such that (P+Q)n+P≤t<(P+Q)(n+1), Takahashi is awake.

He can get off the train at Town B if it is stopping at Town B and he is awake.Determine whether he can get off at Town B. If he can, find the earliest possible time to do so.Under the constraints of this problem, it can be proved that the earliest time is an integer.

You are given T cases. Solve each of them.

Sample Input 1

1
2
3
4
3
5 2 7 6
1 1 3 1
999999999 1 1000000000 1

Sample Output 1

1
2
3
4
Copy
20
infinity
1000000000999999999

拓展欧几里得~
题目就是求一个同余方程组：

两式相减可以得：

因为题目中的 $Y,Q$ 都比较小，所以 $t1,t2$ 可以暴力遍历，上式可以通过拓展欧几里得定理求得一个特解 $x_0$，所以可以得到 $t$ 的一个特解 $t_0=(2X+2Y)*x_0+t1$，那么通解就是 $t=t_0+LCM(2X+2Y,P+Q)$，题目要求最小的正整数解，只需要将特解 $t_0$ 对 $LCM(2X+2Y,P+Q)$ 取模即可~
这题唯一的坑点就是会爆 $ll$，所以在最后算答案的时候要加快速乘，AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll X, Y, ans, LCM, x, y, p, q, i, j;

void Gcd(ll A, ll B, ll &gcd) {
    if (B) {
        Gcd(B, A % B, gcd);
        ll t = X;
        X = Y;
        Y = t - (A / B) * Y;
    } else {
        gcd = A;
        X = 1, Y = 0;
    }
}

ll f(ll a, ll b, ll mod) {
    ll k = 0;
    while (b) {
        if (b & 1) k = (k + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return k;
}

void exgcd(ll A, ll B, ll C) {
    ll gcd;
    Gcd(A, B, gcd);
    if (C % gcd) return;
    else {
        X = X * (C / gcd);
        if (X < 0) X = (LCM - (-X) % LCM) % LCM;
        ans = min(ans, (f(2 * x + 2 * y, X, LCM) + i) % LCM);
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        ans = INT64_MAX;
        cin >> x >> y >> p >> q;
        LCM = (2 * x + 2 * y) / __gcd(2 * x + 2 * y, p + q) * (p + q);
        for (i = x; i < x + y; i++) {
            for (j = p; j < p + q; j++) {
                exgcd(2 * x + 2 * y, -p - q, j - i);
            }
        }
        if (ans == INT64_MAX) cout << "infinity\n";
        else cout << ans << endl;
    }
    return 0;
}

发表于 分类于 Valine：

题目链接

给你两个长度可能不等的整数数组 nums1 和 nums2 。两个数组中的所有值都在 1 到 6 之间（包含 1 和 6）。

每次操作中，你可以选择 任意 数组中的任意一个整数，将它变成 1 到 6 之间 任意 的值（包含 1 和 6）。

请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等，请返回 -1 。

示例 1：

1
2
3
4
5
6
输入：nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums2[0] 变为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[5] 变为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[2] 变为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。

示例 2：

1
2
3
输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6]
输出：-1
解释：没有办法减少 nums1 的和或者增加 nums2 的和使二者相等。

示例 3：

1
2
3
4
5
6
输入：nums1 = [6,6], nums2 = [1]
输出：3
解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums1[0] 变为 2 。 nums1 = [2,6], nums2 = [1] 。
- 将 nums1[1] 变为 2 。 nums1 = [2,2], nums2 = [1] 。
- 将 nums2[0] 变为 4 。 nums1 = [2,2], nums2 = [4] 。

二分~

容易想到二分次数，但是 check 函数比较难想，我们要先计算两个数组和的差值 res，如果次数为 x，试想，我们必须要用 x 次操作使得两个数组的和尽可能接近，一次操作变化的最大值有下面两种情况：

  • 将数组和较大的数组 v1 按从大到小排序，变化的最大值即为 v1.front()-1
  • 将数组和较大的数组 v2 按从小到大排序，变化的最大值即为 6-v2.front()

基于上述的分类，我们可以开两个指针 l1,l2 指向两个数组的开头，在二分的过程中判断是否能让 res=0 即可，AC 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    bool check(int x, vector<int> &nums1, vector<int> &nums2, int res) {
        int l1 = 0, l2 = 0, cnt = 0;
        while (res > 0) {
            if (l1 < nums1.size() && l2 < nums2.size()) {
                if (nums1[l1] - 1 >= 6 - nums2[l2]) {
                    res -= nums1[l1] - 1;
                    l1++;
                    cnt++;
                } else {
                    res -= 6 - nums2[l2];
                    l2++;
                    cnt++;
                }
            } else if (l1 < nums1.size()) {
                res -= nums1[l1] - 1;
                l1++;
                cnt++;
            } else if (l2 < nums2.size()) {
                res -= 6 - nums2[l2];
                l2++;
                cnt++;
            } else break;
        }
        return (cnt <= x);
    }

    int minOperations(vector<int> &nums1, vector<int> &nums2) {
        int mn1 = nums1.size(), mx1 = nums1.size() * 6;
        int mn2 = nums2.size(), mx2 = nums2.size() * 6;
        int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
        int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
        if (sum1 < sum2) swap(nums1, nums2);
        sort(nums1.rbegin(), nums1.rend());
        sort(nums2.begin(), nums2.end());
        int res = abs(sum1 - sum2);
        if (mn2 > mx1 || mn1 > mx2) return -1;
        int l = 0, r = nums1.size() + nums2.size();
        while (l <= r) {
            int mid = l + r >> 1;
            if (check(mid, nums1, nums2, res)) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }
};

发表于 分类于 Valine：

题目链接

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

示例 1：

1
2
3
输入：s = "aaabb", k = 3
输出：3
解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2：

1
2
3
输入：s = "ababbc", k = 2
输出：5
解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

双指针~
这题的关键在于怎么利用双指针找答案，我一开始判断的条件就是两根指针划定的区间的子串每个字符的出现次数，后来发现它并不满足临界点的性质，比如示例2，当子串为 $abab$ 时是满足的，$ababb$ 也是满足的，所以我们无法判断其中一个指针是否到达了临界点~
对此我们可以再限制一个条件，就是字符的种类数 $i$，当前子串的种类数大于 $i$ 时，证明已达临界点，我们就可以移动另一个指针了，中间的判断一样，我们可以遍历每一种字符的个数，判断是否满足条件；为了节省时间空间，我们可以开一个 $less$ 变量记录字符的种类数，当某一字符的出现次数达到 $k$ 时，就减 $1$，这样当 $less=0$ 时，一定满足该子串所有字符的出现次数大于等于 $k$~
AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int longestSubstring(string s, int k) {
        int ans = 0;
        int n = s.length();
        for (int i = 1; i <= 26; i++) {
            int l = 0, r = 0;
            vector<int> cnt(26, 0);
            int tot = 0, less = 0;
            while (r < n) {
                cnt[s[r] - 'a']++;
                if (cnt[s[r] - 'a'] == 1) {
                    tot++;
                    less++;
                }
                if (cnt[s[r] - 'a'] == k) less--;
                while (tot > i) {
                    cnt[s[l] - 'a']--;
                    if (cnt[s[l] - 'a'] == k - 1) less++;
                    if (cnt[s[l] - 'a'] == 0) tot--, less--;
                    l++;
                }
                if (!less) ans = max(ans, r - l + 1);
                r++;
            }
        }
        return ans;
    }
};