题解：P7542 [COCI2009-2010#1] MALI

xuchenxi · 2024-07-23 12:01:16 · 题解

题目传送门

题意理解

给定两个数组 A _ {i} 和 B _ {i} 。对于任意 1\le k \le n ，将前 k 组数两两配成 k 个数对 (A _ {i} , B _ {j}) 。求出所有数对的和 (A _ {i} ^ {} + B _ {j} ^ {}) 中最大值的最小可能值。

题目分析

一道贪心的好题。

贪心结论

升序排序后将 A _ {i} 和 B _ {n-i+1} 配成一对最优。

结论证明

不妨设 A _ {i} 是 A 中最大的元素， B _ {j} 是 B 中最小的元素。

若将 B _ {j} 替换为 B _ {k} ^ {} (B _ {j} \le B _ {k}) ，则 A _ {i} + B _ {k} \ge A _ {i} + B _ {j} 。即替换后不优于替换前，得证。

暴力解法: 50pts

输入 A _ {i} 和 B _ {i} 后直接排序, 暴力查找数对和的最小值，复杂度 O(n _ {} ^ {2} \log{n}) 。

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
int n;
int a[maxn],b[maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        sort(a+1,a+i+1);
        sort(b+1,b+i+1);
        int ans=0;
        for(int j=1;j<=i;j++)
        ans=max(ans,a[j]+b[i-j+1]);
        cout<<ans<<"\n";
    }
    return 0;
}

正解：桶排序

上面的暴力显然会超时。

优化：

• 观察到 n 的范围虽然很大，但 A _ {i} 和 B _ {i} 的范围极小，所以想到桶排序。
• 将和相同的数对预处理掉一部分。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int maxa=105;
int n;
int a,b;
int x[maxa],y[maxa];
int cnta[maxa],cntb[maxa];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int ans=0;
        cin>>a>>b;
        cnta[a]++,cntb[b]++;
        for(int j=1;j<maxa;j++)
        {
            x[j]=cnta[j];
            y[j]=cntb[j];
        }
        int l=1;
        int r=100;
        while(l<=100)//优化1
        {
            while(!x[l] && l<=100) l++;
            while(!y[r] && r>=1) r--;
            if(l>100) break;
            ans=max(ans,l+r);
            int g=min(x[l],y[r]);//优化2
            x[l]-=g;
            y[r]-=g;
        }
        cout<<ans<<"\n";
    }
    return 0;
}

END