AP325 Q-3-14. 線性函數(@@)

tags: 程式設計

online judge: TCIRC
link: https://judge.tcirc.tw/ShowProblem?problemid=d038

題目敘述

有

$N$ 線性函數

$f_i(x)=a_{i}x+b_i，1\le i\le N$。定義

$F(x)=ma{x}_i{f}_i(x)$。輸入

$c[i],1\le i\le m$，請計算

$\sum _{i=1}^{n}F(c[i])$。

輸入說明

第一行是

$N$ 與

$m$。接下來有

$N$ 行，依序每行兩個整數

$a_i$ 與

$b_i$，最後一行有

$m$個整數

$c[1],c[2],\cdots ,c[m]$。每一行的相鄰數字間以空白隔開。

$N\le {10}^5$，

$m\le 5\times {10}^4$，輸入整數絕對值不超過

${10}^7$，答案不超過

${10}^{15}$。

範例輸入

4 5
-1 0
1 0
-2 -3
2 -3
4 -5 -1 0 2

範例輸出

15

範例的圖

AP325的提示

想法

先找到提示中，組成紅色線的那些線，並把其他不相關的線刪掉，再記錄紅色線轉彎地方的點的

$x$座標，以知道哪些

$c[i]$要用哪一條線去算

$y$值，最後再將

$c[i]$由小到大，依序求解。

1.尋找符合的線

維護一個stack，裡面的線皆是當前的解，依斜率由小到大加入，如果即將加入的線，比他前面的線還好時，就可以把前面的線pop掉。

• 如何判斷當前的線是否比上一條好?

數字代表放入stack的順序，令

$x_{a,b}$代表直線a和直線b交的

$x$座標。
當直線3沒有比直線2好的時候，如左圖，

$x_{1,2}<x_{2,3}$。
而直線3比直線2好的時候，如右圖，

$x_{1,2}>x_{2,3}$。
所以得到一個結論，當

$x_{n-1,n-2}>x_{n,n-1}$，直線n-1就不會是可以找到最大值的線。

• 例外
  當兩直線平行時，會找不到兩線所交的點，此時就按照兩線的
  $b$來比，較大的會在較上面，所以就捨棄掉較小的。

2.找到各c[i]的最大y值

過濾掉一些不會用到的線之後，用一個陣列去紀錄線與線之間的

$x$座標，去找

$c[i]$所對應到的直線，並帶入求解。(參考Code 67 ~ 73行)

Code

#include<iostream>
#include<algorithm>
#define a first
#define b second
#define x first
#define y second
#define MAX_N 100020
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;

pll line[MAX_N];
pll dq[MAX_N]; // actually it's a stack
ll C[MAX_N];
double pos[MAX_N];

int lf = 0, rt = 0;

pdd getPoint(pll p1, pll p2) {
	pdd res;
	double a1 = p1.a, b1 = p1.b;
	double a2 = p2.a, b2 = p2.b;
	res.x = (b2 - b1) / (a1 - a2);
	res.y = (a2*b1 - a1*b2) / (a2 - a1);
	return res;
}

bool discardLast(int idx) {
	if (line[idx].a == dq[rt-1].a) {
		return true;
	}
	pdd p = getPoint(line[idx], dq[rt-1]);
	pdd lp = getPoint(dq[rt-1], dq[rt-2]);
	if (p.x > lp.x) {
		return false;
	} else {
		return true;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, M;
	cin >> N >> M;
	for (int i = 0;i < N;i++) {
		cin >> line[i].a >> line[i].b;
	}
	for (int i = 0;i < M;i++) {
		cin >> C[i];
	}
	sort(line, line+N);
	sort(C, C+M);
	for (int i = 0;i < N;i++) {
		while (rt - lf >= 2 && discardLast(i)) {
			--rt;
		}
		dq[rt++] = line[i];
	}
	for (int i = lf, idx = 0;i <= rt-2;i++, idx++) {
		pdd p = getPoint(dq[i], dq[i+1]);
		pos[idx] = p.x;
	}
	ll ans = 0;
	int idx = 0;
	for (int i = 0;i < M;i++) {
		while (idx < rt-lf-1 && C[i] > pos[idx]) {
			idx++;
		}
		pll p = dq[lf+idx];
		ans += (p.a*C[i] + p.b);
	}
	cout << ans << '\n';
	return 0;
}

Result

• 最後更新 Fri, Sep 24, 2021 10:54 AM