大二上开学第二周

约 1155 字大约 4 分钟

2025-09-21

第二周强度继续加大，这周做的力扣题也相对每那么水了。

题目

加油站

力扣134，中等难度，主要思路是贪心。这题比较难的部分在于状态的确认，即确认什么时候油量会小于0以及从何处出发可以避免油量小于0。贪心我们不具体证明了。我们首先检查第0个加油站，并试图判断能否环绕一周；如果不能，就从第一个无法到达的加油站开始继续检查。

答案如下：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();

        int i = 0;

        while (i < n) {
            int s1 = 0, s2 = 0;
            int cnt = 0;
            while (cnt < n) {
                s2+=cost[(i + cnt) % n];s1+=gas[(i + cnt) % n] ;
                
                if (s1 < s2) break;
                cnt++;
            }
            if (cnt == n) {
                return i;
            }
            i = i + cnt + 1;
        }
        return -1;
    }
};

奶牛转向

洛谷绿题，哥们这辈子没做过这么难的，体面如下：

P2882 [USACO07MAR] Face The Right Way G

题目描述

$N$ 头牛排成一列。每头牛要么向前要么向后。为了让所有牛都面向前方，农夫每次可以将 $K$ 头连续的牛转向（ $1 \le K \le N$ ），求最小的操作次数 $M$ 和相应的最小 $K$ 。

输入格式

第一行一个正整数 $N$ 。

下面 $N$ 行，每行一个字符 F 或 B，表示一头奶牛的初始朝向。（F 为朝前，B 为朝后）

输出格式

请在一行输出两个数字 $K$ 和 $M$ ，用空格分开。

输入输出样例 #1

输入 #1

7
B
B
F
B
F
B
B

输出 #1

3 3

说明/提示

样例解释： $K=3$ ， $M=3$ ， $3$ 次操作分别让奶牛 $1/2/3,\ \ 3/4/5,\ \ 5/6/7$ 转向。

对于 $100\%$ 的数据， $1 \le N \le 5000$ 。

说实在题解我都看得不是很明白。这题难点有两个，第一个是要想到其中的贪心，第二个是你得掌握数组差分，不然大概率爆TLE。

首先把输入的内容预处理，这部分我们就不写了，太基础。我们把输入存进vector<int>，0代表朝后，1代表朝前。

一开始我没看系统底下给的提示（尝试遍历 $k$ ），反而是尝试先判断出 $M$ 是多少。正常来做应该是直接从小到大遍历 $k$ ，每次循环都判断是否能够翻转成功。如果成功，那么将当前 $M$ 和 $k$ 更新，失败则继续。 $k$ 的范围是 $[1,\ vector.size()]$ 。

那么在每个循环中要如何判断当前 $k$ 能否翻转成功呢？观察可得，对一个奶牛翻转两次等效于没有翻转，所以从左到右对于出现的每一个B翻转一次，每次翻转 $k$ 个，然后下一次翻转的位置就是当前数组（翻转过的）下一个为B的地方。常规来讲我们会再嵌套一层循环，但是这样时间复杂度就会来到 $O(n^3)$ ，经测试无论是在洛谷还是学校平台都会爆。所以我们要用到差分的技巧。

差分就是创建一个等大小的辅助数组，用以记录相邻单元间值的差，这样就可以通过对差分求和以得到任意单元的值，十分便于对数组某个连续范围的值进行修改。

代码如下

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    std::vector<int> milk(0);

    while (n--) {
        char ch;
        std::cin >> ch;
        switch (ch) {
            case 'B':
            milk.push_back(0);
            break;
            case 'F':
            milk.push_back(1);
        }
    }

    int mincnt {0x7ffff};
    int k;


    for (int i = 1; i <= milk.size(); i++) {
        std::vector<int> cha(milk.size() + 2, 0);
        std::vector<int> copy(milk);
        int cnt = 0;
        int judge = 1;
        int b = 0;
        for (int j = 0; j < copy.size(); j++) {
            b ^= cha[j];
            if (copy[j] == b) {
                if (j + i > milk.size()) {
                    judge = 0;
                    break;
                }
                b ^= 1;
                cha[j + i] ^= 1;
                cnt++;
            }

        }
        if (judge) {
            if (cnt < mincnt) {
                mincnt = cnt;
                k = i;
            }
        }
        
    }
    std::cout << k << " " << mincnt;

}