放牧代码和思想
专注自然语言处理、机器学习算法

POJ 1180 Batch Scheduling​ 题解《挑战程序设计竞赛》

目录

hankcs.com 2017-01-19 上午1.28.15.png挑战程序设计竞赛第二版.jpg

POJ 1180 Batch Scheduling 

批任务调度:N个顺序任务,分别耗时Ti,权重Fi。 若批处理,每批任务耗时S+Ti之和,同批次任务视作同时完成。总耗时等于每个任务完成的时刻乘以其权重,求最少耗时?

4.4常用技巧精选(二) 

双端队列 

最朴素的思路就是dp了,定义

dp[i] := 从任务i到N的最少耗时

从后往前递推,有状态转移方程

dp[j] = min(dp[j], t * f + dp[j + i]);

其中f是从j到N的F之和,相对于i来讲是个常量。t是从j到N的T之和,随着i增加。

看起来是个O(n2)的糟糕算法,也的确会TLE。

但擦亮眼睛,剑走偏锋,题目的数据范围给的很清楚

1 <= N <= 10000
0 <= S <= 50
1 <= Ti <= 100

S最多相当于一个批次执行时间的1/200,暗示着一个批次不会超过200个任务。于是限制一下搜索分支,就水过去了。

#include <iostream>
using namespace std;
const int MAX_N = 10000 + 8;
int S, N;
int T[MAX_N], F[MAX_N];
int sum_F[MAX_N];
int dp[MAX_N];
int solve()
{
    for (int j = N - 1; j >= 0; --j)
    {
        int f = sum_F[N] - sum_F[j], t = S;
        for (int i = 1; j + i <= N && i <= 200; i++)
        {
            t += T[j + i - 1];
            dp[j] = min(dp[j], t * f + dp[j + i]);
        }
    }
    return dp[0];
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d%d", &N, &S);
    memset(dp, 0x3f, N * sizeof(int));
    for (int i = 0; i < N; ++i)
    {
        scanf("%d%d", T + i, F + i);
        sum_F[i + 1] = sum_F[i] + F[i];
    }
    printf("%d\n", solve());
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}
16491862 hankcs 1180 Accepted 320K 63MS C++ 776B 2017-01-18 11:37:56

想走正道的话,老老实实地用双端队列吧。

定义

dp[i] := 从 1 ~ i 的最小耗时贡献

这里贡献的意思是,假设任务i到N存在但是T=0,任务1到i的最小耗时。比如说假设一共2个任务,每个任务独占一个批次

dp[1] = (f1+f2)*t1+S*(f1+f2)
dp[2] = min{dp[1] + f2*(t1+t2), dp[1] + f2*t2} = dp[1] + f2*t2

这个min的意思是,有两个分支,前者将两个任务放到一个批次中,后者放到两个批次中。

虽然看起来没什么规律,但我们稍微变一下形式

sum_F[i] := F的前i项之和,同理定义sum_T
dp[0] = 0
dp[1] = (sum_F[N)-sum_F[0])*sum_T[1]+dp[0]+(S-sum_T[0])*(sum_F[N]-sum_F[0])
dp[2] = (sum_F[N)-sum_F[1])*sum_T[2]+dp[1]+(S-sum_T[1])*(sum_F[N]-sum_F[1])

就能抽象出一条直线来:

dp[i] = min{k[1~i]*sum_T[1~i]+b[1~i]}
k[i] = sum_F[N] - sum_F[i-1]
b[i] = dp[i-1]+(S-sum_T[i-1])*(sum_F[N]-sum_F[i-1])

其实蛮好理解的,假设dp[i]->dp[j],那么k[i]*sum_T[1~i]表示1~i-1的T都会累积到i~N的任务上去,这还不够,还需要加上b[i]。b[i]中的dp[i-1]是前i-1个任务的最小耗时贡献,后面是一个对贡献的修正。

上面的dp方程跟书上是类似的

dp[i]=S[i]+min{fj(i)|0≤j≤i-k}

其中f是关于dp的直线方程,直接利用书上的结论就行了。

hankcs.com 2017-01-19 上午1.28.07.png

hankcs.com 2017-01-19 上午1.28.15.png

#include <iostream>
#include <deque>

using namespace std;

// (k, b) := 直线kx+b
struct Line
{
    int k, b;

    Line(int k, int b) : k(k), b(b)
    {}
};

const int MAX_N = 10000 + 8;
int N;
int S;
int sum_T[MAX_N];
int sum_F[MAX_N];
int dp[MAX_N];              // dp[i] := 从 1 ~ i 的最小耗时贡献


int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d%d", &N, &S);
    for (int i = 1; i <= N; i++)
    {
        scanf("%d%d", sum_T + i, sum_F + i);
        sum_T[i] += sum_T[i - 1];
        sum_F[i] += sum_F[i - 1];
    }
    deque<Line> lines;
    lines.push_back(Line(sum_F[N], S * sum_F[N]));
    for (int i = 1; i <= N; i++)
    {
        int k1, b1;
        int k2, b2;
        int k3, b3;

        while (lines.size() > 1)
        {
            k1 = lines[0].k;
            b1 = lines[0].b;
            k2 = lines[1].k;
            b2 = lines[1].b;
            if (k1 * sum_T[i] + b1 >= k2 * sum_T[i] + b2)
                lines.pop_front();  // 若头部的值不是最小值了则删去
            else
                break;
        }

        k1 = lines[0].k;
        b1 = lines[0].b;
        dp[i] = k1 * sum_T[i] + b1;
        k3 = sum_F[N] - sum_F[i];
        b3 = dp[i] + (S - sum_T[i]) * (sum_F[N] - sum_F[i]);

        while (lines.size() > 1)
        {
            k1 = lines[lines.size() - 2].k;
            b1 = lines[lines.size() - 2].b;
            k2 = lines[lines.size() - 1].k;
            b2 = lines[lines.size() - 1].b;
            if ((k2 - k1) * (b3 - b2) >= (b2 - b1) * (k3 - k2)) // tail不可能成为最小值的直线
                lines.pop_back();
            else
                break;
        }

        lines.push_back(Line(k3, b3));
    }

    printf("%d\n", dp[N]);
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}
16492080 hankcs 1180 Accepted 296K 63MS C++ 1727B 2017-01-18 12:47:35

虽然从运行时间上来看并无卵用。

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 1180 Batch Scheduling​ 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机