QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#481803#5137. Tower333zhanWA 6ms3820kbC++201.8kb2024-07-17 14:23:122024-07-17 14:23:12

Judging History

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

  • [2024-07-17 14:23:12]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:3820kb
  • [2024-07-17 14:23:12]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long

using namespace std;

inline int read () {
    int w = 1, s = 0; char ch = getchar ();
    for (; ! isdigit (ch); ch = getchar ()) if (ch == '-') w = -1;
    for (; isdigit (ch); ch = getchar ()) s = (s << 1) + (s << 3) + (ch ^ 48);
    return s * w;
}

void solve () {
    int n = read (), m = read ();

    vector <int> all;
    vector <int> a (n);
    for (int i = 0; i < n; i ++) {
        a[i] = read ();
        int t = a[i];
        while (t) {
            all.push_back (t);
            t /= 2;
        }
    }

    sort (all.begin (), all.end ());
    all.erase (unique (all.begin (), all.end ()), all.end ());

    int ans = 1E18;

    for (auto x : all) {
        vector <int> b;
        for (int y : a) {
            int sum = 0;
            if (y <= x) {
                sum = abs (x - y);
            } else {
                int s1 = 0, s2 = 0;
                int t1 = y, t2 = y;
                while (t1 >= y) {
                    if (t1 / 2 < x) {
                        t1 /= 2;
                        s1 ++;
                        break;
                    }
                    t1 /= 2;
                    s1 ++;
                    t2 /= 2;
                    s2 ++;
                }
                sum = min (s1 + abs (x - t1), s2 + abs (x - t2));
            }
            b.push_back (sum);
        }
        sort (b.begin (), b.end (), greater ());
        int sum = accumulate (b.begin (), b.end (), 0LL);
        for (int i = 0; i < m; i ++) {
            sum -= b[i];
        }
        ans = min (ans, sum);
    }

    printf ("%lld\n", ans);
} 

signed main () {
	// ios::sync_with_stdio (false);
    // cin.tie (nullptr);
    
	int T = 1; 
	// cin >> T;
	T = read ();

	while (T --) {
		solve ();
	}
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3772kb

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: 6ms
memory: 3820kb

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:

737
3
723
160
848
1720
2287
437
1395
50

result:

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