[数据结构与算法]#806.宝箱 思维

Link
思维
两天因为INF = 0x3f3f3f3f 不够大被卡了两次，，看来如果不涉及运算的话还是得设一个更大的值。

题意

思路

感冒了，好难受，回头补一下

简单来说就是如果当前走到第 $i$ 个点，遇到的宝箱数多于钥匙数，那么有两种选择

1. 走到下一个钥匙之后立即折返，那么 $i$ 到 $i+1$ 这段路一定被走了3遍。
2. 走到尽头再折返，相当于之后的所有路都走了2遍

所以就是枚举每个点选择1优还是选择2优。
显然2最多只会选一次，所以选择一定形如1112或者11111，只要枚举在哪个点选2，并一直记录每步选1的当前距离就行了。

代码

int b[maxn], c[maxn];
int n;
struct Node {
    int t;    //1宝箱 2钥匙
    int dis;
    bool operator < (const Node &x) const {
        if(dis != x.dis)
            return dis < x.dis;
        return t > x.t;
    }
};
int f[maxn];	//f[i]表示i - i+1 这段走几遍
int cot[3];	//cot[1]表示经过的宝箱数量，2表示钥匙
void solve() {
    cin >> n;
    vector<Node> v;
    v.push_back(Node{0, 0});
    for(int i = 1; i <= n; i++) {
        cin >> b[i];
        v.push_back(Node{1, b[i]});
    }
    for(int i = 1; i <= n; i++) {
        cin >> c[i];
        v.push_back(Node{2, c[i]});
    }
    sort(v.begin(), v.end());
    f[1] = 1;
    int mx = max(b[n], c[n]);
    int ans = INF;
    int len = 0; //假设上述每步都选1，记录了走到i点的距离
    for(int i = 1; i < v.size(); i++) {
        len += f[i] * (v[i].dis - v[i-1].dis);
        ans = min(ans, len + 2 * (mx - v[i].dis));//尝试如果该步选择2的距离，取min
        cot[v[i].t]++;
        if(cot[1] > cot[2]) f[i+1] = 3;
        else f[i+1] = 1;
    }
    cout << ans << endl;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖