P5948 [POI2003]Chocolate

· · 题解

Solution

我们将题目简化为：现有集合 X,Y，里面有已有一些数字。

我们观察题目，不难得出每次切割的代价为，其数值与前面不属于同个集合的数字个数 +1 的乘积。

例如，若横向切下一刀，此时巧克力变为两块，那么竖向切割时就需要切两次，即做两倍代价。以此类推，即可得出上述结论。

进一步分析，我们不难得出应优先选择数值大的进行切割。

对于同个集合，显然数值大的排序靠前更优。

对于不同集合，即不同方向上切割，后切的自然需要在原基础上多切一刀，那么数值大的会越来越大。反之，我们则需要优先选择数值大的。

因此，我们可以将两个集合合并、排序后进行操作。

时间复杂度为 O(N \log{N})，可以通过本题。

Code

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e4+5;  //注意开两倍大小
int n,m,tot,x_,y_;
long long ans;
struct qwq{
    int val,id;
}a[N];
bool cmp(qwq x,qwq y){
    return x.val>y.val;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<n;i++){
        cin>>a[i].val;
        a[i].id=1;
    }
    for(int i=n;i<n+m-1;i++){
        cin>>a[i].val;
        a[i].id=2;
    }
    tot=n-1+m-1;
    sort(a+1,a+1+tot,cmp);
    for(int i=1;i<=tot;i++){    //记录出现过的不同元素
        if(a[i].id==1) ans+=(y_+1)*a[i].val,x_++;
        else ans+=(x_+1)*a[i].val,y_++;
    }
    cout<<ans<<endl;
    return 0;
}