二分题瞬间变成简单DP题

作者: | 更新日期:

思维很重要,但是就是没想到这么简单的方法。

本文首发于公众号:天空的代码世界,微信号:tiankonguse

一、背景

在《2021 TPC 腾讯程序设计竞赛(1)》比赛中,第四题蚂蚁报团取暖大家都是使用二分来做的。

后来,有人分享了一个动态规划的想法,一听,发现这道题瞬间变得好简单。

下面就把这个想法分享给大家吧。

二、报团取暖

题意:在横坐标轴上给 n 个蚂蚁的坐标。 为了报团取暖,蚂蚁每秒可以左右移动一个单位。 问最少过多少秒,每个蚂蚁方圆 d 单位内至少有一个蚂蚁。

分析:既然是报团取暖,那有人提出,两两抱团或者两三报团是最优的。。

所以这道题就类似于走楼梯的题,走两阶或者走三阶,找最优值。

状态转移方程:

dp(i) = min(dp2(i), dp3(i))
dp2(i) = max(dp(i-2), cal(i, 2));
dp3(i) = max(dp(i-3), cal(i, 3));
cal(i, k) 最近 k 个人报团取暖的最优值

可以发现,当前状态dp(i)的最优值是最后两个人报团取暖或最后三个人报团取暖的最小值。

而最近两个人报团取暖后,这两个人时间就固定了,所以总的时间就是谁的耗时长取谁。

代码:

int str[max5];
double dp[max5];  // 最近两个报团的最优解 VS 最近三个报团的最优解
int d;

double solve2(int x, int y) { return max(y - x - d, 0) / 2.0; }

double solve3(int x, int y, int z) {
  return (max(y - x - d, 0) + max(z - y - d, 0)) / 2.0;
}

double dfs2(int i) { return max(dp[i - 2], solve2(str[i - 1], str[i])); }
double dfs3(int i) {
  return max(dp[i - 3], solve3(str[i - 2], str[i - 1], str[i]));
}

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d%d", &n, &d);
    for (int i = 1; i <= n; i++) {
      scanf("%d", &str[i]);
    }
    sort(str + 1, str + n + 1);

    dp[0] = 0;
    dp[1] = inf;  // 一个无解,设置为最大值
    dp[2] = dfs2(i);  

    for (int i = 3; i <= n; i++) {
      dp[i] = min(dfs2(i), dfs3(i));
    }
    printf("%.6f\n", dp[n]);
  }
  return 0;
}

三、最后

仔细想想这道题,还是思维转的不够快。

报团取暖,至少两个人就行了。

这意味着更多的报团可以拆分为若干个两两或者两三报团。

进而得出结论两两或者两三报团最优的。

只可惜我是想不到这个,以后还是要多练习吧。

加油,算法人。

《完》

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
QQ算法群:165531769(不止算法)
知识星球:不止算法

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越