经典算法题

2026-02-06

均分纸牌

[传送门](P1031 [NOIP 2002 提高组] 均分纸牌 - 洛谷)

题意：

现有$n$堆纸牌，需要让每堆纸牌牌数相等。相邻的纸牌堆可以交换任意个纸牌，求最小交换次数

样例

4
9 8 17 6

平均数为$10$ 显然可以有$17$往左移动两次，往右移动一次得到答案

思路：

贪心不妨先用每堆牌数减去平均数，这样每一堆转换为多/少出来的牌数

可以从左往右遍历整个数组，如果当前需要的牌数不为$0$，说明需要移动。并把所有需要的牌数转移到下一堆上。

代码：

n=int(input())
a=list(map(int,input().split()))
ans=0
sum=0
for x in a:
    sum+=x
ave=sum//n
for i in range(0,n):
    a[i]-=ave
for i in range(0,n):
    if a[i]:
        a[i+1]+=a[i]
        ans+=1
        a[i]=0
print(ans)

环形问题

[传送门](P2512 [HAOI2008] 糖果传递 - 洛谷) 是纸牌问题的另一种形式

此时$n$堆牌围成一个圈，可以向左/右传递牌

思路：

如果原数组为$A$，平均数为$ave$ 设$X_i$为每一堆牌往左传递的个数，往右传递记为负数

对于$i (1\leq i \lt n)$ , 有$A_i-X_i+X_{i+1}=ave$ 有$A_n - X_n + X_1=ave$

即$X_i = X_{i-1}+ ave - A_{i-1}$ $X_2 = X_1+ave-A_1$ $X_3 = X_2+ave-A_2 = X_1+2ave-A_1-A_2$ $X_n =X_1+(n-1) ave - A_1 - A_2 …-A_{n-1}$ $X_1 = X_n+ ave -A_n = X_1 + nave - A_1…A_n$

令$C_i = -i ave + A_1 .. +A_i$ 则$X_i = X_1-C_{i-1}$ , $X_1 = X_1-C_n$

目标要求$X_i$的绝对值之和最小

即$|X1-C_{i-1}|$的和最小

因此问题转换为货舱选址问题预处理出$C$数组，令$X_1$为其中位数即可

n=int(input())
a=list(map(int,input().split()))
sum=0
for x in a:
    sum+=x
k=sum//n
ans=0
c=[0]*(n+1)
lst=0
for i in range(1,n+1):
    lst+=a[i-1]
    c[i]=-i*k+lst
c[1:n+1]=sorted(c[1:n+1])
x1 = c[(n+1)//2]
for i in range(1,n+1):
    ans+=abs(x1-c[i])
print(ans)

区间合并

多米诺骨牌_牛客题霸_牛客网

考虑这样的问题：给定一个数轴上的若干区间$[l_i,r_i]$，将互相有重叠部分的区间合成一个大区间，最后的大区间有多少个？

做法：

将$[l_i,r_i]$从小到大排序（先按左端点从左到右，再按右端点从左到右）
遍历区间，如果当前区间的左端点$l$小于等于正在合并的区间的右端点$r$，那么合并，将$r$设置为当前区间的右端点和$r$的最大值

#include <bits/stdc++.h>
#define int long long
using namespace std;
int t;
void solve(){
    int n,m;cin>>n>>m;
    vector<int>h(n+1),x(n+1);
    for(int i=1;i<=n;i++)cin>>h[i];
    for(int i=1;i<=n;i++)cin>>x[i];
    vector<pair<int,int>>v(n+1);
    for(int i=1;i<=n;i++){
        v[i]={x[i],x[i]+h[i]};
    }
    sort(v.begin()+1,v.end());
    int l=v[1].first,r=v[1].second;
    vector<int>vec;
    int lst = 1;
    for(int i=2;i<=n;i++){
        if(v[i].first<=r){
            lst++;
            r=max(r,v[i].second);
        }else{
            vec.push_back(lst);
            lst=1;
            l=v[i].first;
            r=v[i].second;
        }
    }
    vec.push_back(lst);
    sort(vec.begin(),vec.end(),greater<int>());
    int ans = 0;
    for(int i=0;i<min(m,(int)vec.size());i++){
        ans+=vec[i];
    }
    cout<<ans<<endl;
}
signed main() {
    cin>>t;
    while(t--)solve();
}

区间并查集

小苯的蓄水池（hard）_牛客题霸_牛客网

const int M= 2e5+5;
int f[M];
int sz[M];
int a[M];
int find(int x){
    if(f[x]!=x){
        f[x]=find(f[x]);
    }return f[x];
}
void merge(int x,int y){
    if(find(x)!=find(y)){
        if(x>y)swap(x,y);
        int px=find(x),py=find(y);
        f[px]=f[py];
        a[py]+=a[px];
        sz[py]+=sz[px];
    }
}
signed main() {
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        sz[i]=1;
        f[i]=i;
    }
    for(int i=1;i<=m;i++){
        int opt;cin>>opt;
        if(opt==1){
            int l,r;cin>>l>>r;
            for(int i=find(l);i<r;i=find(i)){
                merge(i,i+1);
            }
        }else{
            int q;cin>>q;
            cout<<fixed<<setprecision(10)<<a[find(q)]*1.0/sz[find(q)]<<endl;
        }
    }
}