CF1311D. Three Integers 2000 ——数学 + 枚举

D. Three Integers

题意：

给出a, b, c 3个数(a<=b<=c<=1e4), 每次操作可以对任意一个数减1或者+1，问使得bmoda cmodb == 0的操作数最少是多少？

思路：

从1，2a遍历a，对每个a，遍历<=2b的a的倍数作为b，c取c/b*b or c/b*b+b，

取最小值，时间复杂度O(nlogn).

// Decline is inevitable,
// Romance will last forever.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define mst(a, x) memset(a, x, sizeof(a))
#define INF 0x3f3f3f3f
//#define mp make_pair
#define pii pair
#define fi first
#define se second
#define ll long long
//#define int long long
const int maxn = 2e5 + 10;
const int maxm = 1e3 + 10;
const int P = 1e9 + 7;
int n, m;
int a, b, c;
void solve() {
    cin >> a >> b >> c;
    if(c % b == 0 && b % a == 0) {
        cout << 0 << endl;
        cout << a << ' ' << b << ' ' << c << endl;
        return;
    }
    int tmp = INF;
    int ans[3];
    for(int i = 1; i <= 2*a; i++) {
        for(int j = i; j <= 2*b; j += i) {
            int c1 = c/j * j;
            int c2 = (c/j+1) * j;
            int ans1 = abs(a-i) + abs(b-j) + abs(c1-c);
            int ans2 = abs(a-i) + abs(b-j) + abs(c2-c);
            if(ans1 < tmp) {
                ans[0] = i; ans[1] = j; ans[2] = c1;
                tmp = ans1;
            }
            if(ans2 < tmp) {
                ans[0] = i; ans[1] = j; ans[2] = c2;
                tmp = ans2;
            }
        }
    }
    cout << tmp << endl;
    for(int i = 0; i < 3; i++)
        cout << ans[i] << ' ';
    cout << endl;
    
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int T; scanf("%d", &T); while(T--)
    int T; cin >> T; while(T--)
    solve();
    return 0;
}

CF1311D. Three Integers 2000 ——数学 + 枚举

C/C++/C#相关栏目本月热门文章