D - Three Integers

https://codeforces.com/contest/1311/problem/D

本题题意：给出a,b,c三个数，a<=b<=c；

可以对三个数中任意一个进行+1或-1的操作；

问题：求出最少操作数使这些数满足：b整除a,c整除b

思路：题目中给出abc的范围只有1e4

所以我们可以通过枚举的方式来找出答案；

我们通过枚举b的大小，然后计算在b为k值得情况下，a,c为哪个数最优

暴力枚举出最优情况即可；

细节：在枚举b为k时，对于a，我们可以通过预处理出b的因子，然后枚举因子与原本的数的差值，找出最优即可；

而对于c,有以下情况：

1.对于b>c的情况，我们只需要让c等于b

2.对于c>b的情况，我们有两种可能，1.c已经整除b,这种需要的操作数为0

　　　　　　　　　　　　　　　　 2.c没整除b,所以可能让c减少到为b的倍数，或者增大到b的倍数，两者枚举找操作数小的即可；

所以这道题的做法就是：先预处理出范围内的因子，然后枚举；

代码如下：

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 #define me(a,x) memset(a,x,sizeof a)

 #define rep(i,x,n) for(int i=x;i<n;i++)

 #define repd(i,x,n) for(int i=x;i<=n;i++)

 #define all(x) (x).begin(), (x).end()

 #define pb(a) push_back(a)

 #define paii pair<int,int>

 #define pali pair<ll,int>

 #define pail pair<int,ll>

 #define pall pair<ll,ll>

 #define fi first

 #define se second

 vector<int>g[];

 int a,b,c;

 void inist()

 {

     for(int i=;i<=;i++){

         for(int j=;j<=/i;j++)

             g[i*j].pb(i);

     }

 }

 int work(int& aa,int bb,int& cc)

 {

     int ans=;

     int minn=;

     int l=g[bb].size();

     int x=aa;

     for(int i=;i<l;i++){

         if(minn>abs(g[bb][i]-aa)){

             minn=abs(g[bb][i]-aa);

             x=g[bb][i];

         }

     }

     aa=x;

     ans+=minn;

     if(bb>cc){

         ans+=abs(bb-cc);

         cc=bb;

     }

     if(cc%bb<bb-cc%bb){

         ans+=cc%bb;

         cc-=cc%bb;

     }

     else{

         ans+=bb-cc%bb;

         cc+=bb-cc%bb;

     }

     return ans;

 }

 int main()

 {

     inist();

     int t;

     cin>>t;

     while(t--){

         int ans=;

         int ansa,ansb,ansc;

         cin>>a>>b>>c;

         for(int i=;i<=;i++){

             int a1=a,b1=i,c1=c;

             int temp=abs(i-b);

             temp+=work(a1,b1,c1);

             if(temp<ans){

                 ans=temp;

                 ansa=a1;ansb=b1;ansc=c1;

             }

         }

         cout<<ans<<endl;

         cout<<ansa<<" "<<ansb<<" "<<ansc<<endl;

     }

     return ;

 }

巴特西

D - Three Integers

最新文章

热门文章