20分TLE求助
查看原帖
20分TLE求助
762928
Runtime_Error754楼主2023/6/6 19:44
对于一个整数 x,定义其极差 f(x) 为其十进制表示中最大数码和最小数码的差。例如:f ( 5 2 3 ) = 5 − 2 = 3 f(523)=5−2=3 ( 1 0 1 0 0 9 ) = 9 − 0 = 9 f(101009)=9−0=9 现在给出一个范围 [ , ] [l,r],请你找出其中 f(x) 值最小的 x,若有多个输出 x 最小的。 输入格式 第一行 1 1 个整数 t,代表有 t 组数据 。 接下来 t 行,每行 2 2 个整数 , l,r 代表一组询问 。 输出格式 输出 t 行,每行 1 1 个整数代表答案 。 样例 #1 样例输入 #1 5 59 63 42 49 48 53 90 90 1 100 样例输出 #1 63 44 53 90 1 样例输入 #2 10 174308965148379901 175057038026166289 117303861557273283 118157788606119311 109238775272796427 109937866294793617 844116675381148012 844263441994971408 427067669145289375 428007891549800252 868268147295988618 868677964360581411 387533226681484699 387964502314669916 473074827648495068 473846504477860320 107862743381764509 108682397396275087 416115159908374436 416283295282599394 样例输出 #2 174311111111111111 117311111111111111 109238775272796427 844222222222222222 427222222222222222 868666666666666666 387533333333333333 473333333333333333 107862743381764510 416115161111111111 提示 对于 2 0 % 20% 的数据, 1 ≤ l ≤ r ≤ 10^3 1≤l≤r≤10 ^3 。 对于 50% 的数据, 1≤l≤r≤10 ^6 。 对于 70% 的数据, 1≤l≤r≤10 ^9 。 对于 100% 的数据, 1≤t≤100,1≤l≤r≤10^18 。

我都用了快速幂了啊!

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll powx(ll b,ll p)
{
 	ll ans=1;
 	while(p)
 	{
 		if(p&1) ans*=b;
		 p/=2;
		 b*=b;
	 }
	return ans;
}
ll f(ll l,ll r)
{
    if(l<=9) return l;
    else
    {
    ll g=LONG_LONG_MAX,idx=0;
        for(ll i=l;i<=r;i++)
        {
            ll m=LONG_LONG_MIN,mi=LONG_LONG_MAX;
            for(ll j=0;j<=ll(log10(i));j++)
            {
                if(j<18)
                {
                int u=powx(10,j),u2=u*10;
                m=max(m,i%u2/u),mi=min(mi,i%u2/u);
                }
                else
                {
                    int u=powx(10,j);
                    m=max(m,i/u),mi=min(mi,i/u);
                }
            }
            bool flag=(g!=abs(m-mi));
            g=min(g,abs(m-mi));
            if(flag&&g==abs(m-mi)) idx=i;
        }
        return idx;
    }
}
int main()
{
 	ios::sync_with_stdio(0);
 	cin.tie(0),cout.tie(0);
    ll t,l,r;
    cin>>t;
    for(ll i=1;i<=t;i++) cin>>l>>r,cout<<f(l,r)<<endl;
	return 0;
}

2023/6/6 19:44
加载中...