1

我正在尝试解决 spoj ( MPILOT ) 上的问题。

我知道这是一个动态编程问题，我也尝试过，但它给了我一个错误的答案。我的方法是获取飞行员和助理的工资差异并按降序排序，然后0 - N/2添加为assistant和N/2+1 - N添加为pilot并输出sum。但问题在于飞行员必须比助理年长的年龄条件。

这是我的代码

#include <iostream>
#include <vector>
#include <algorithm>
#define lint long long

using namespace std;

struct pilot {
lint pilotsal;
lint assistantsal;
lint diff;
};

bool compare (pilot p1, pilot p2)
{
 return (p1.diff > p2.diff);
}

int main()
{
lint c,n,i;
lint sum=0,max=0;
 cin >> n;
vector <pilot> pilots(n);
for(i=0;i<n;i++)
{
    cin >> pilots[i].pilotsal >> pilots[i].assistantsal;
    pilots[i].diff= pilots[i].pilotsal-pilots[i].assistantsal;
}
 sum = max = pilots[0].assistantsal;
 sort(pilots.begin()+1,pilots.end(),compare);
for(i=1;i<=n/2-1;i++)
{
    sum+=pilots[i].assistantsal;
}

for(i=n/2;i<n;i++)
{
    sum+=pilots[i].pilotsal;
}
   cout << sum << endl;
   return 0;
}

请给我一些提示。如何检查问题的年龄条件。

4

1 回答 1

3

在尝试使用“动态编程”解决这个问题一个小时后，我得出结论认为这不是合适的方法，但问题还没有解决。我想到了许多贪婪的想法，但在大多数情况下贪婪并不好。

最后我无法解决这个问题，但由于这个问题很有趣，我确实搜索了解决方案，这是我对解决方案的理解：

飞行员按升序排列：

  • 第一个飞行员必须是助理
  • 最后一名飞行员必须是船长

最糟糕的解决方案是我们支付所有飞行员（机长和助手）为机长。这将是我们的第一个解决方案，我们将尝试将这个数量减少到最低限度。

我们可以从把船长变成助手的过程中节省Pilot.CaptainWage - Pilot.AssistantWage下来。

问题变得很容易，因为只需要最低工资，而不是分组本身。

1. Set the first pilot as assistant
2. Insert each pilot in a list from the second to the last, and for every 2 new elements in the list
  // One pilot can be turned to an assistant only if remains at least another older pilot
  2.1 Select the pilot who contribute with the maximum saving so far
  2.2 Rest the saving of the previous step to our original solution
  2.3 Remove the pilot from the list
3. Print our new solution

注意：您需要一个高效的数据结构来以快速的方式获得最大节省的 Pilot，可能是heap。

看看你是否可以通过这个找到解决方案。我不会发布指向实际解决方案的链接，因为如果您先自己尝试会更好:)。

于 2013-05-01T19:23:04.373 回答