鐘凡收據的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。

在解题之前提交题解的代码会导致封禁。

Subtask 1~4

取 \(x\) 和 \(y\) 陣列的前綴和（partial_sum），枚舉時間 \(k\)，\(O(nq)\)。（TLE 80%）

Subtask 1~5

Solution 1

顯然最值對應的時間點 \(f(a)\) 對 \(a\) 有單調性，i.e. 對任意 \(a \le a'\)，\(f(a) \le f(a')\)。（可以想像為前半的 \(a \sum y_i\) 越大，後面就越有餘裕減掉 \(\sum x_i\)。）

令 \(g(a', k')\) 為 \(a = a', 時間點 = k'\) 的 \(a \sum y_i - \sum x_i\) 值。
\(\forall 0 \le x \lt f(a)\) 時 \(g(a, f(a)) - g(a, x) \ge 0 \)。又， \[ g(a + 1, f(a)) - g(a + 1, x) \\ = g(a, f(a)) + \sum_{i=1}^{f(a)} y_i - g(a, x) - \sum_{i=1}^x y_i \\ = g(a, f(a)) - g(a, x) + \sum_{i=x+1}^{f(a)} y_i \\ \ge 0 \] 即 \(f(a)\) 必優於 \(x\) \(\Rightarrow\) \(f(a + 1) \ge f(a)\)，得證。

因此可以進行整體二分，\(O(qlgn)\)。（AC 100%）

Solution 2

可以發現取前綴和後，此題能轉換為「給 \(n\) 條直線 \(y=Ax+B\)，詢問 \(x=a\) 時 \(y\) 的最大值」，也就是經典的凸包/斜率優化，\(O(qlgn)\)。（AC 100%）

（詳情可見這份建中講義的 3.1。）

標程

C++ 斜率優化（by tan7680）

#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
long long x[maxn],y[maxn],t[maxn],c=0;
int main()
{
    cin.tie(0);ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++)x[i]+=x[i-1];
    for(int i=1;i<=n;i++)y[i]+=y[i-1];
    t[c++]=0;
    for(int i=1;i<=n;i++)
    {
        while(c>1&&(x[t[c-1]]-x[t[c-2]])*(y[i]-y[t[c-1]])>=(y[t[c-1]]-y[t[c-2]])*(x[i]-x[t[c-1]]))c--;
        t[c++]=i;
    }
    int Q;
    cin>>Q;
    while(Q--)
    {
        long long a;
        cin>>a;
        int l=0,r=c-1;
        while(l<r)
        {
            int m=(l+r)/2;
            if((x[t[m+1]]-x[t[m]])>=(y[t[m+1]]-y[t[m]])*a)r=m;
            else l=m+1;
        }
        cout<<a*y[t[l]]-x[t[l]]<<'\n';
    }
return 0;
}

C++ 整體二分（by WillyPillow）

#include <bits/stdc++.h>
using namespace std;

int64_t ans[1000000], sumX[1000001], sumY[1000001];
pair<int, int> query[1000000];

void cdq(int l, int r, int ansL, int ansR) {
    if (l > r) return;
    int m = (l + r) >> 1;
    pair<int64_t, int> tmp = {-1E9, 0};
    for (int i = ansL; i <= ansR; i++) {
        tmp = max(tmp, {query[m].first * sumY[i] - sumX[i], -i});
    }
    ans[query[m].second] = tmp.first;
    cdq(l, m - 1, ansL, -tmp.second), cdq(m + 1, r, -tmp.second, ansR);
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> sumX[i] >> sumY[i];
    for (int i = 1; i <= n; i++) sumX[i] += sumX[i - 1], sumY[i] += sumY[i - 1];
    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> query[i].first;
        query[i].second = i;
    }
    sort(query, query + q);
    cdq(0, q - 1, 0, n);
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

Scala 整體二分（by WillyPillow）

object x002 extends App {
  def readL() = io.StdIn.readLine().split(" ").map(_.toInt)
  def readLL() = io.StdIn.readLine().split(" ").map(_.toLong)

  val n = io.StdIn.readInt()
  val xy = Array.fill(n)(readLL())
    .scan(Array(0L, 0))((acc, cur) => Array(acc(0) + cur(0), acc(1) + cur(1)))
  val q = io.StdIn.readInt()
  val query = readL().zipWithIndex.sorted

  def cdq(qs: Seq[(Int, Int)], vs: Seq[Array[Long]]): Vector[(Int, Long)] =
    if (qs.isEmpty) Vector.empty
    else {
      val (l, r) = qs.splitAt(qs.size / 2)
      val (ans, idx) = vs.map(v => r.head._1 * v(1) - v(0)).zipWithIndex.max
      cdq(l, vs.take(idx + 1)) ++ cdq(r.tail, vs.drop(idx)) :+ (r.head._2, ans)
    }

  cdq(query.view, xy.view).sorted foreach (x => println(x._2))
}

目前没有评论。