algorithm - 寻找产生最低工资的安排

Question

我又一次被 sopj 问题困住了 pilots

问题陈述是..

查理收购了航空运输公司，为了继续经营下去，他需要千方百计降低开支。他的公司有 N 名飞行员(N 为偶数)，需要培养 N/2 名机组人员。机组人员由两名飞行员组成 - 一名机长和他的助手。船长必须比他的助手年长。每个飞行员都有一份契约(Contract)，授予他两种可能的薪水——一种是机长，另一种是助理。同一个飞行员，机长的薪水比副手的多。但是，助理的薪水可能比他的队长高。编写一个程序，计算如果查理决定花一些时间对飞行员进行最优(即最便宜)的机组安排，他需要为飞行员的薪水支付的最低金额。

输入

第一行输入整数N，2≤N≤10000，N为偶数，查理公司的飞行员人数。接下来的 N 行输入包含飞行员的薪水。这些行按飞行员的年龄排序，最年轻的飞行员的薪水排在第一位。这 N 行中的每一行包含两个由空格字符分隔的整数，X i Y，1 ≤ Y < X ≤ 100,000，船长的薪水 (X) 和助理的薪水 (Y)。

输出

输出的第一行也是唯一一行应该包含 Charlie 需要为飞行员的工资支付的最少金额。

示例

输入

4 
5000 3000 
6000 2000 
8000 1000 
9000 6000 

输出19000

输入

6 
10000 7000 
9000 3000 
6000 4000 
5000 1000 
9000 3000 
8000 6000 

输出32000

现在我正在使用一个贪婪的方法，因为很明显第一个飞行员应该是助理，然后我检查是否可以通过让飞行员担任机长来省钱，如果是的话，那么我会让他成为机长，其他人则是助理.

它在大多数情况下都能完美工作，但我得到了一个错误的 awnser。

我的代码是..

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i,n) for(int i=0;i<n;i++)

int main()
{
    int n;
    //freopen("input.txt","r",stdin);
    cin>>n;
    vector<pair<pii,int> > data;
    FOR(i,n)
    {
        int csal,asal;
        cin>>csal>>asal;
        int diff=csal-asal;
        data.pb(mp(mp(csal,asal),diff));
    }
    int ccount=0,acount=0,sal=0;
    FOR(i,n)
    {
        if(acount<n/2)
        {
            int flag=1;
            for(int j=i+1;j<=i+(acount-ccount);j++)
            {
                if(data[i].se<=data[j].se)
                {
                    //cout<<j<<" ";
                    flag=0;
                    break;
                }
            }
            if(flag)
            {
                sal+=data[i].fi.se;
                acount++;
            }
            else
            {
                sal+=data[i].fi.fi;
                ccount++;
            }
        }
        else
        {
            sal+=data[i].fi.fi;
                ccount++;
        }
        //cout<<sal<<" "<<i<<"\n";
    }
    cout<<sal<<"\n";
    return 0;
}

请帮我解决这个问题..

Answer 1

这是一个运行时间为 O(N log N) 的解决方案。它使用贪心算法，但它与你的不同。

1) 假设 delta[i] = X[i] - Y[i]。
2) 现在让我们处理按 delta[i] 降序排列的飞行员。我们将假设所有飞行员最初都被赋予机长职位。
3)如果可能的话，每个飞行员都应该重新分配到助理职位。
就是这样。我声称这个算法总是给出正确的结果。

证明:
1)当飞行员不能担任助理工作时？
i) 当他右边(按年龄)没有“空闲”队长时(即如果他右边的队长人数大于或等于助手人数)。为什么会这样？除非他右边有“太多”助手。让我们假设我们决定修复它。这将需要将一名助手更换为船长。但如果飞行员是助理，则他在现任飞行员之前得到处理。这意味着他的 delta 更大(回想一下我们按排序顺序迭代它们)。再观察一下:一个助手只能挡住一个船长(因为船员只有一个船长)。这两个观察表明，在无法使当前飞行员成为助手的情况下进行某些更改只会使答案变得更糟。
ii) 当他被他左边(按年龄计算)的助手接任为队长时。要修复它，有必要让那个人再次成为船长，就像在 i) 中一样。这只会使答案变得更糟(证明与上述情况相同)。
2)利用数学归纳法和以上两个观察，可以严格证明该算法是正确的。
3)该算法总是会产生恰好 N/2 个助手，因为它会尽可能让飞行员成为助手，并且恰好有 N/2 种可能性。

剩下的唯一问题是:如何检查是否可以让当前飞行员成为助手？
这是一个快速的方法:让我们为每个飞行员分配 1，如果他是机长，否则分配 -1。我们来看看这个-1和1的数组，按照飞行员的年龄排序。我声明，如果有后缀为负数，则配置无效。否则，它是有效的(这个陈述并不难证明，但我不会在这里张贴证据或者我的答案中有太多证据)。所以我们需要维护两个操作:将 -1 更改为 1(反之亦然)并判断是否存在与负和的后缀。这是一个标准问题，可以用线段树解决(可以在每个节点中存储总和和最小后缀和，更新很容易，因为一次只改变一个元素的值(即叶子中的一个值)).

复杂度为 O(N log N) 因为我们需要对数组进行排序，并且在迭代过程中，每一步最多对线段树执行 3 次查询(并且每个查询需要 O(log N) 时间)。