QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#647614#5137. TowerbhscerWA 143ms3828kbC++172.6kb2024-10-17 14:56:372024-10-17 14:56:37

Judging History

你现在查看的是最新测评结果

  • [2024-10-17 14:56:37]
  • 评测
  • 测评结果:WA
  • 用时:143ms
  • 内存:3828kb
  • [2024-10-17 14:56:37]
  • 提交

answer

#include <bits/stdc++.h>

#define int long long
#define fadd(a,b,c) for (int a=b;a<=c;a++)
#define fsub(a,b,c) for (int a=b;a>=c;a--)
#define F first
#define S second
#define CYes cout << "Yes\n"
#define CNo cout << "No\n"
#define CYES cout << "YES\n"
#define CNO cout << "NO\n"
#define println(a) cout << (a) << '\n'

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
void fastIO(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
class bhscer {
public:
    template<typename FIRST, typename ...PACK> static void debug(FIRST first, PACK... params) { std::cout<< first <<' '; debug(params...);}
    template<typename T> static void debug(T end) { std::cout << end << std::endl; }
};
const int N = 5e5;
int a[N];

int cal(int x, int y) {
    if (x >= y) {
        return x - y;
    }

    if (x == 0) {
        int res = 0;
        while (y) {
            res ++;
            y /= 2;
        }
        return res;
    }
    // y > x
    int res = 1e17;
    int step = 0;
    int mx = x, my = y;

    while (y*2 >= x) {
        res = min(res, step + abs(y - x));
        x *= 2;
        step++;
    }

    x = mx; y = my;
    step = 0;
    while (y >= x) {
        res = min(res, step + abs(y - x));
        step ++;
        if (y == 0) break;
        y /= 2;
    }
    return res;
}
void solve() {
    int n,m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int ans = 1e17;
    for (int i=1;i<=n;i++) {
        int x = a[i];

        // cout << " > " << x << endl;
        while (true) {
            // cout << "all be " << x << endl;
            priority_queue<int, vector<int>, greater<int>> q;
            int curCost = 0;
            for (int j=1;j<=n;j++) {

                // cout << "  " << a[j] << " " <<  cal(x, a[j]) << endl;
                if (j == i) {
                    curCost = cal(x, a[j]);
                } else {
                    q.push(cal(x, a[j]));
                }
            }
            int cur = curCost;
            for (int j=1;j<=n-m-1;j++) {
                cur += q.top();
                q.pop();
            }

            ans = min(ans, cur);
            // cout << x << endl;
            if (x == 0) break;
            x /= 2;
            // cout << " -> " << x << endl;
        }
    }
    println(ans);
}
signed main() {
    fastIO();
    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
//        int x,y; cin >> x >> y;
//        println(cal(x,y));
    }

    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3612kb

input:

3
2 0
2 6
5 0
1 2 3 4 5
5 3
1 2 3 4 5

output:

2
4
1

result:

ok 3 number(s): "2 4 1"

Test #2:

score: -100
Wrong Answer
time: 143ms
memory: 3828kb

input:

10
272 118
11 14 49 94 71 62 46 45 74 22 15 36 7 37 27 35 96 85 75 78 76 64 23 59 17 35 71 28 96 82 5 66 2 48 57 31 88 10 61 73 79 23 19 52 39 76 48 98 5 39 48 51 90 90 60 27 47 24 24 56 48 27 39 21 38 18 20 9 62 83 47 15 51 22 73 74 7 80 64 60 86 74 59 7 84 38 99 31 42 60 52 41 63 88 59 90 77 40 68...

output:

477
3
466
114
589
659
1037
235
674
52

result:

wrong answer 1st numbers differ - expected: '454', found: '477'