AGC011E Increasing Numbers

题目链接

发现每个“递增的”数一定可以拆成这样 (9) 个数：$ egin{matrix}underbrace{111cdots111} pend{matrix}$。

假设我们现在选择了 (k) 个递增的数，那么有 (n=sumlimits_{i=1}^{9k}frac{10^{p_i-1}}9)。

也就是说 (9n+9k=sumlimits_{i=1}^{9k}10^{p_i})。右边的意思就是说，进行 (9k) 次操作，每次操作可以在任意位上 (+1)。所以只要 (9n+9k) 上的所有数字之和 (leq 9k) 就行了。显然这个 (k) 可以二分。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<ctime>
#define PB push_back

using namespace std;

const int N = 500009, base = 10;
typedef vector <int> num;
char s[N];
int sum;

int count(int x);

num read()
{
	num A; A.clear();
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	while (1)
	{
		A.PB(0);
		if (n > 1)
		{
			for (int i = n; i <= n; i++) A.back() = A.back() * 10 + s[i] - '0';
			n -= 1;
		}
		else
		{
			for (int i = 1; i <= n; i++) A.back() = A.back() * 10 + s[i] - '0';
			break;
		}
	}
	return A;
}

num operator + (num A, int B)
{
	for (int i = 0; i < A.size(); i++)
	{
		if (!B) return A;
		sum -= count(A[i]), A[i] += B;
		B = A[i] / base, A[i] %= base;
		sum += count(A[i]);
	}
	if (B)
		A.PB(B), sum += count(A.back());
	return A;
}

num operator * (num A, int B)
{
	if (A.empty()) return A;
	for (int i = 0; i < A.size(); i++)
		A[i] *= B;
	int w = 0;
	for (int i = 0; i < A.size(); i++)
		A[i] += w, w = A[i] / base, A[i] %= base;
	while (w)
		A.PB(w % base), w /= base;
	return A;
}

int count(int x)
{
	if (x < 10) return x;
	int tmp = 0;
	while (x)
		tmp += x % 10, x /= 10;
	return tmp;
}

void print(num A, char c)
{
	printf("%d", A.back());
	for (int i = (int)A.size() - 2; i >= 0; i--)
		printf("%d", A[i]);
	putchar(c);
}

void work()
{
	num A = read();
	A = A * 9;
	sum = 0;
	for (int i = 0; i < A.size(); i++)
		sum += count(A[i]);
	int tmp = sum;
	int l = 1, r = 500000, mid;
	while (l <= r)
	{
		mid = l + r >> 1;
		sum = tmp;
		num B = A + mid * 9;
		if (sum <= 9 * mid)
			r = mid - 1;
		else
			l = mid + 1;
	}
	printf("%d
", l);
}

int main()
{
	work();
	return 0;
}