• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

CF1408D Searchlights

开发技术 开发技术 4小时前 1次浏览

CF1408D Searchlights

题意:

在以左下角 ((0 , 0)) 为坐标原点的直角坐标系中 , 有 (n) 个强盗 (m) 个监控。每个监控能看到自己左下角的所有区域。而所有强盗可以且只能同时向右或向上移动一步,求为了让所有强盗摆脱监控,最少移动次数为多少。

解法:

实际上这道题的图最终会形成这样:

CF1408D Searchlights

观察可知,从上往下 (x) 轴能延伸到的位置单调递增。而且在上下两个相邻监控之间的部分,能延伸到的部分相同。

我们开一个数组 (f_i) 表示所有海盗先向上走了 (i) 步之后,最少要向右走几步。

处理这个数组需要的复杂度为 (O(nm)) ,具体实现如下:

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(a[i] > c[j]) continue;
        f[c[j] - a[i]] = max(f[c[j] - a[i]] , d[j] - b[i] + 1);
    }
}

然后再根据 (x)(y) 单调递减可以得到:

(y) 越大,那么需要向右平移的位置越少。

所以我们就得到了以下写法:

int ans = 1e9 , last = 0;
for(int i=MAXN;i>=0;i--){
    last = max(last , f[i]);
    ans = min(ans , i + last);
}

时间复杂度:

令 N = 1e6。

总复杂度为 (O(nm + N))

Code


程序员灯塔
转载请注明原文链接:CF1408D Searchlights
喜欢 (0)