(*2400) Codeforces Round 185 (Div. 1) B. Cats Transport

原题链接：https://codeforces.com/contest/311/problem/B

B. Cats Transport

题目描述

沿路有$n(2\le n\le 10^5)$座土堆，第$i-1$和第$i$座土堆之间的距离为$d_i(1\le d_i \lt 10^4)$米，有$m(1\le m\le 10^5)$只猫，第$j$只猫在$t_j(0\le t_j\le 10^9)$时刻走到土堆$h_j(1\le h_j\le n)$上，然后在该土堆上等待，饲养员从第一个土堆出发，速度为$1$米/单位时间，按顺序从$1$到$n$走过所有土堆，如果$t$时刻到了第$j$座土堆，猫已经在这座土堆上了，则将这只猫带走，猫的等待时间为$t-t_j$，共有$p(1\le p \le 100)$个饲养员，求将所有猫带走总等待时间最小是多少

示例

输入

4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12

输出

3

说明

共有4座土堆，6只猫，2个饲养员；4座土堆的距离土堆$0$的距离可以记为$[0,1,4,9]$，猫到各个土堆的时刻为$[[0,10],[1,10],[12],[9]]$

第一个饲养员$0$时刻出发，到达$4$座土堆的时间分别是$[0,1,4,9]$，带走$3$只猫，等待时间为$0$

剩余$3$只猫：$[[10],[10],[12],[]]$，第$2$个饲养员$10$时刻出发，到达时间为$[10,11,14,19]$，带走剩余$3$只猫，等待时间为$(11-10)+(14-12)=3$，即为最小等待时间

解决方案

将猫在各个土堆上的时间减去该土堆距离土堆$0$的距离，并从小到大排序，得到$a=[0,0,0,8,9,10]$，表示从土堆$0$触发的时刻需要大于等于该值，才能够接到对应的猫，假如出发的时刻为$T$，则对应的等待时间为$T-a[i]$；现在用数组$a$的下标来代表对应的猫，可以观察到，如果出发时刻为$a[i]$，则$\le i$的所有猫都必定可以被接走，且早接走必定比晚接走等待时间短；因此可以得到如下的转移公式：($dp[p][i]$表示有$p$个饲养员时，最小的等待时间，$sum[i]$表示$a[1]+a[2]+...+a[i]$)

$dp[p][i]=min(dp[p-1][j]+a[i]*(i-j)-(sum[i]-sum[j])), j<i$

$dp[p][i]=min((-j)*a[i]+dp[p-1][j]+sum[j])+a[i]*i-sum[i], j<i$

朴素的时间复杂度为$O(p*m*m)$，利用凸包技巧Convex Hull Trick，可以将时间复杂度优化到$O(p*m)$

时间复杂度

$O(p*m)$

代码

#include <bits/stdc++.h>
 
using namespace std;
 
template <typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
 
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif

template<typename T>
struct Line {
    T k, b;
    // 集合中的直线按照斜率从小到大排序，该值表示本直线与下一条直线的交点的横坐标
    mutable T intersect_x;
    bool operator<(const Line<T>& o) const { return k < o.k; }  // 用于按照斜率排序
    bool operator<(T x) const { // 用于在Query时进行二分查找
        return intersect_x < x;
    }                                                  // 用于二分查找
    T Eval(T x) const { return k * x + b; }  // 求直线在x点的y值
    T IntersectX(const Line<T>& line) const { // 求与直线line的交点的横坐标
        assert(k != line.k); // 斜率不能相等，否则除0异常
        return Div(line.b - b, k - line.k);
    }
    T Div(T a, T b) const {
        if constexpr (std::is_integral<T>::value) {
            // floored division,
            // 因为两条直线之间的交点可能是小数，但是x是整数，因此小数部分永远不会取到
            // 所以求直线交点时只需要记录<=交点横坐标值的最大整数即可
            // 3/2 -> 1; -3/2 -> -2; 4/2 -> 2; -4/2 -> 2
            return a / b - ((a ^ b) < 0 && a % b);
        } else {
            return a / b;
        }
    }
};

// IS_SORTED=1表示插入和查询是按照斜率排好序的顺序进行的，n条直线的时间复杂度为O(n)
// IS_SORTED=0表示插入和查询默认是无序的，内部使用multiset排序，n条直线的时间复杂度为O(n*logn)
template <typename T, int IS_SORTED = 0, int FIND_MIN = 0>
class LineContainer {
   public:
    void Add(T k, T b) {
        if (FIND_MIN) Add(Line<T>{-k, -b, 0});
        else Add(Line<T>{k, b, 0});
    }
    // 查找使得k*x+b最大的那条直线并返回最大的k*x+b
    T Query(T x) {
        // assert(!lines.empty());
        if (lines.empty())
            return FIND_MIN ? numeric_limits<T>::max() : numeric_limits<T>::lowest();
        auto l = lines.lower_bound(x);
        return FIND_MIN ? -(l->Eval(x)) : l->Eval(x);
    }
    size_t Size() {
        return lines.size();
    }
    void Swap(LineContainer<T, IS_SORTED, FIND_MIN>& other) {
        lines.swap(other.lines);
    }
    void Merge(const LineContainer<T, IS_SORTED, FIND_MIN>& other) {
        for (auto line : other.lines) {
            Add(line);
        }
    }
   private:
    void Add(const Line<T>& line) {
        auto nxt = lines.insert(line), cur = nxt++, prev = cur;
        // 判断插入的直线后面的直线是否需要删除，如果删除则重新求相邻直线的交点
        while (Intersect(cur, nxt)) nxt = lines.erase(nxt);
        // 判断插入的直线本身是否需要删除，删除的话重新求相邻直线的交点
        if (prev != lines.begin() && Intersect(--prev, cur))
            Intersect(prev, cur = lines.erase(cur));
        // 判断插入的直线前面的那一条直线是否需要删除，删除的话重新求相邻直线的交点
        while ((cur = prev) != lines.begin() &&
               (--prev)->intersect_x >= cur->intersect_x)
            Intersect(prev, lines.erase(cur));
    }
    // 求直线l1与l2的交点横坐标（向下取整），并判断是否需要删除直线l2
    bool Intersect(typename multiset<Line<T>>::iterator l1, typename multiset<Line<T> >::iterator l2) {
        if (l2 == lines.end()) {
            l1->intersect_x = numeric_limits<T>::max();
            return false;
        }
        if (l1->k == l2->k) {
            l1->intersect_x = l1->b > l2->b ? numeric_limits<T>::max()
                                            : numeric_limits<T>::lowest();
        } else {
            l1->intersect_x = l1->IntersectX(*l2);
        }
        return l1->intersect_x >= l2->intersect_x;
    }
    multiset<Line<T>, less<>> lines;
};

template <typename T, int FIND_MIN>
class LineContainer<T, 1, FIND_MIN> {
   public:
    void Add(T k, T b) {
        if (FIND_MIN) Add(Line<T>{-k, -b, 0});
        else Add(Line<T>{k, b, 0});
    }
    // 查找使得k*x+b最大的那条直线并返回最大的k*x+b
    T Query(T x) {
        // assert(!lines.empty());
        if (lines.empty())
            return FIND_MIN ? numeric_limits<T>::max() : numeric_limits<T>::lowest();
        T ans;
#define QUERY_INCREASE
#ifdef QUERY_INCREASE
        while (lines.size() >= 2 && lines[0].Eval(x) <= lines[1].Eval(x)) {
            lines.pop_front();
        }
        ans = lines.front().Eval(x);
#elif defined(QUERY_DECREASE)
        while (lines.size() >= 2 && lines[lines.size() - 1].Eval(x) <= lines[lines.size() - 2].Eval(x)) {
            lines.pop_back();
        }
        ans = lines.back().Eval(x);
#else
        auto l = lower_bound(lines.begin(), lines.end(), x);
        ans = l->Eval(x);
#endif
        return FIND_MIN ? -ans : ans;
    }
    size_t Size() {
        return lines.size();
    }
    void Swap(LineContainer<T, 1, FIND_MIN>& other) {
        lines.swap(other.lines);
    }
   private:
    void Add(const Line<T>& line) {
        if (lines.empty()) {
            lines.emplace_back(line);
            lines.back().intersect_x = numeric_limits<T>::max();
        }
        else {
#define ADD_INCREASE
#ifdef ADD_DECREASE
            if (line.k == lines[0].k) {
                if (line.b > lines[0].b) lines.pop_front();
                else return;
            }
            while (lines.size() >= 2 && lines[0].IntersectX(line) >= lines[0].IntersectX(lines[1])) {
                lines.pop_front();
            }
            lines.emplace_front(line);
            lines[0].intersect_x = lines[0].IntersectX(lines[1]);
#elif defined(ADD_INCREASE)
            if (line.k == lines.back().k) {
                if (line.b > lines.back().b) lines.pop_back();
                else return;
            }
            while (lines.size() >= 2 && lines[lines.size()-1].IntersectX(line) <= lines[lines.size()-1].IntersectX(lines[lines.size()-2])) {
                lines.pop_back();
            }
            lines.emplace_back(line);
            lines[sz(lines)-2].intersect_x = lines[sz(lines)-2].IntersectX(lines[sz(lines)-1]);
            lines.back().intersect_x = numeric_limits<T>::max();
#endif
        }
    }
    deque<Line<T>> lines;
};

class Solution {
public:
    void Solve() {
        int n, m, p;
        while(cin>>n>>m>>p) {
            vector<ll> d(n); 
            rep(i,1,n) cin>>d[i];
            rep(i,1,n) d[i] += d[i-1];

            vector<ll> a(m);
            ll h, t;
            rep(i,0,m) {
                cin>>h>>t;
                a[i] = t - d[h-1];
            }
            sort(all(a));
            dbg(a);

            vector<ll> sum(m);
            sum[0] = a[0];
            rep(i,1,m) sum[i] = sum[i-1]+a[i];

            vector<vector<ll>> dp(p, vector<ll>(m));
            rep(j,0,m) dp[0][j] = a[j] * (j+1) - sum[j];

            rep(i,1,p) {
                LineContainer<ll, 1, 1> lines;
                lines.Add(-(i-1), dp[i-1][i-1] + sum[i-1]);
                rep(j,i,m) {
                    dp[i][j] = lines.Query(a[j]) - sum[j] + a[j] * j;
                    if (j+1 < m) lines.Add(-j, dp[i-1][j] + sum[j]);
                }
            }
            dbg(dp);
            cout << dp[p-1].back() << endl;

            // cout << fixed << setprecision(9) << ans << endl;
        }
    }
private:
};
 
// #define USACO 1
void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO || USACO
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}

int main() {
#if USACO
    set_io("time");
#else
    set_io("tmp");
#endif
    Solution().Solve();

    return 0;
}