Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020 D题题解

将题意转换为一开始(t = 0)，第(i)个操作是令(t leftarrow (a_i + 1) t + (a_i + b_i + 1))。记(A_i = a_i + 1, B_i = a_i + b_i + 1)。问经过最多经过多少次操作后才能使得进行完这些操作后(t leq T)仍然满足。

我们先推一个贪心性质：

若先进行(i)操作，再进行(j)操作时满足条件，且(frac{A_i - 1}{B_i} < frac{A_j - 1}{B_j})，则可以交换(i)，(j)操作的顺序，使得条件仍然满足。

证明：由单调性，只需证明先进行(i)操作再进行(j)操作后的(t)的值大于先进行(j)操作再进行(i)操作后(t)的值。假设一开始的数值为(t)，则第一种操作组合后，数值为(A_iA_jt + A_jB_i + B_j)，第二种操作组合后数值为(A_iA_jt + A_iB_j + B_i)。

由于(A_jB_i + B_j > A_iB_j + B_i)等价于(frac{A_i - 1}{B_i} < frac{A_j - 1}{B_j})，故结论成立！

因此我们可以将这些操作按(frac{A_i - 1}{B_i})从大到小排序，然后设计一个DP。设(f_{i, j})表示进行了前(i)种操作的(j)次后(t)的值最小是多少。我们可以得到一个(O(n^2))做法。注意到我们必定先进行(A_i > 0)的操作，而这样的操作最多进行(O(log T))次。再进行(A_i = 0)的操作时，必定是按照(B_i)从小到大顺序进行。所以我们只需把(A_i > 0)的操作拿来(DP)，并且第二维只考虑到(O(log T))即可获得一个(O(n (log n + log T)))时间的算法。

代码如下：

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

const int N = 200005, M = 40;

template <class T>
void read (T &x) {
	int sgn = 1;
	char ch;
	x = 0;
	for (ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar()) ;
	if (ch == '-') ch = getchar(), sgn = -1;
	for (; '0' <= ch && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
	x *= sgn;
}
template <class T>
void write (T x) {
	if (x < 0) putchar('-'), write(-x);
	else if (x < 10) putchar(x + '0');
	else write(x / 10), putchar(x % 10 + '0');
}

int n, cnt1 = 0, cnt2 = 0;
long long a[N], b[N], f[N][M + 1], t;

struct node {
	long long A;
	long long B;
	bool operator < (node rhs) const {
		long long val1 = (A - 1) * rhs.B;
		long long val2 = (rhs.A - 1) * B;
		return (val1 > val2) || (val1 == val2 && A < rhs.A);
	}
} vec[N];

long long num[N], pre[N];

int main () {
	read(n), read(t);
	for (int i = 1; i <= n; i++) {
		read(a[i]), read(b[i]);
		if (a[i]) {
			node x = {a[i] + 1, a[i] + b[i] + 1};
			vec[++cnt1] = x;
		}
		else num[++cnt2] = b[i] + 1;
	}

	sort(vec + 1, vec + cnt1 + 1);
	sort(num + 1, num + cnt2 + 1);

	pre[0] = 0ll;
	for (int i = 1; i <= cnt2; i++) pre[i] = pre[i - 1] + num[i];

	for (int i = 0; i <= M; i++) f[0][i] = t + 1;
	f[0][0] = 0ll;
	
	for (int i = 1; i <= cnt1; i++) {
		for (int j = 0; j <= M; j++) {
			f[i][j] = f[i - 1][j];
			if (j) f[i][j] = min(f[i][j], vec[i].A * f[i - 1][j - 1] + vec[i].B);
		}
	}

	int ans = 0;
	for (int i = 0; i <= M; i++) {
		if (f[cnt1][i] > t) continue;
		int pos = lower_bound(pre, pre + cnt2 + 1, t + 1 - f[cnt1][i]) - pre - 1;
		ans = max(ans, pos + i);
	}
	write(ans), putchar('
');
	return 0;
}