bzoj 4029 定价

Posted on | Views:

贪心.

乍一看像是数位 $dp$ ,仔细想一下其实只需要枚举每个数就可以了.

暴力枚举定价为 $x$ ,每次用 $x$ 更新答案后,把 $x$ 最低的不为 $0$ 的那一位 $+1$ ,继续枚举,中间的显然都没有 $x$ 优.

每一位最多被加 $10$ 次,时间复杂度 $O(T\cdot 10\log^2 R)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int inf=1e9;
int calc(int x)
{
	while(x%10==0)
		x/=10;
	int p=(x%10==5);
	int a=0;
	while(x)
		x/=10,++a;
	return 2*a-p;
}
int nxt(int x)
{
	int cnt=0;
	while(x%10==0)
		x/=10,++cnt;
	++x;
	while(cnt--)
		x*=10;
	return x;
}
int main()
{
	int T=read();
	while(T--)
	{
		int L=read(),R=read();
		int mi=inf,ans,x=L;
		while(x<=R)
		{
			int val=calc(x);
			if(val<mi)
				mi=val,ans=x;
			x=nxt(x);
		}
		printf("%d\n",ans);
	}
	return 0;
}