Znzryb's Blog
0%

2025牛客WC1-E-双生双宿之错

Posted on Edited on

思路讲解

参考题解：

https://ac.nowcoder.com/discuss/1452661

https://ac.nowcoder.com/discuss/1452662（这个题解好）

中位数定理，其实类似于树的重心（以该点为根，最大子树最小），都是不能牺牲大我

只有一个点左边也有n个点，右边也有n个点，到达该点距离之和最短

其实数轴就是一种特殊的树嘛～～

AC代码

AC https://ac.nowcoder.com/acm/contest/view-submission?submissionId=74961575

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
const ll MAXN=static_cast<ll>(1e5)+10;
ll N,T,A[MAXN];
void solve() {
    cin>>N;
    for(int i=1;i<=N;++i) {
        cin>>A[i];
    }
    sort(&A[1],&A[N+1]);
    // 中位数定理
    ll mid1,mid2;
    if(N%4==0) mid1=A[N/4]+A[N/4+1]>>1,mid2=A[3*N/4]+A[3*N/4+1]>>1;
    else mid1=A[N/4+1],mid2=A[3*N/4+1];	// 是不是严格在中间是不重要的
    if(mid1==mid2) {
        mid1-=1;	// 强制-1（6 6 6 6那个数据）
        ll dis=0,dis2=0;
        for(int i=1;i<=N;++i) {
            if(i<=N/2) {
                dis+=abs(A[i]-mid1);
            }else {
                dis+=abs(A[i]-mid2);
            }
        }
        mid1+=1,mid2+=1;
        for(int i=1;i<=N;++i) {
            if(i<=N/2) {
                dis2+=abs(A[i]-mid1);
            }else {
                dis2+=abs(A[i]-mid2);
            }
        }
        cout<<min(dis,dis2)<<'\n';
        return;
    }
    ll dis=0;
    for(int i=1;i<=N;++i) {
        if(i<=N/2) {
            dis+=abs(A[i]-mid1);
        }else {
            dis+=abs(A[i]-mid2);
        }
    }
    cout<<dis<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while (T--) {
        solve();
    }
    return 0;
}
/*
3
4
1 1 3 1
4
6 6 6 6
6
1 1 4 4 1 4

*/

心路历程（WA，TLE，MLE……）

前面一直有点问题，结果是因为这个特判mid1-=1和mid2+=1都要算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
if(mid1==mid2) {
        mid1-=1;	// 强制-1（6 6 6 6那个数据）
        ll dis=0,dis2=0;
        for(int i=1;i<=N;++i) {
            if(i<=N/2) {
                dis+=abs(A[i]-mid1);
            }else {
                dis+=abs(A[i]-mid2);
            }
        }
        mid1+=1,mid2+=1;
        for(int i=1;i<=N;++i) {
            if(i<=N/2) {
                dis2+=abs(A[i]-mid1);
            }else {
                dis2+=abs(A[i]-mid2);
            }
        }
        cout<<min(dis,dis2)<<'\n';
        return;
    }