动态编程MPILOT

我正试图解决一个关于spoj的问题（MPILOT）。动态编程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; 
}

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

来源

2013-05-01 shahwarcoder

请帮助我一些提示，因为我真的很想解决这个问题。 – shahwarcoder 2013-05-01 14:56:17

感谢您的编辑，可以请你帮我解决。 – shahwarcoder 2013-05-01 17:10:44

我现在正在尝试这个问题，但我无法保证任何事情。 – rendon 2013-05-01 17:26:06

使用“动态规划”试图解决这个问题一小时后，我断定这不是合适的方法，但问题还没有解决。我脑中出现了许多贪婪的想法，但在大多数情况下，贪婪并不好。

最后我解决不了这个问题，但由于这个问题很有意思我也搜索解决方案，这里是我百思不得其解的：

飞行员在升序排序：

的第一个飞行员必须是一个助理
的最后飞行员必须是一个队长

最坏的解决方案是，当我们p所有的飞行员（队长和助手）都是队长。这将是我们的第一个解决方案，我们会尽量减少到最低。

保存我们可以从一个队长转到助理是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

注：您需要一个有效的数据结构，以获得具有最大限度的节省飞行员在一个快速的方式，也许是heap。

看看你是否可以用这个解决方案。我不会将链接发布到实际的解决方案，因为如果您先尝试自己，那么效果会更好:)。

来源

2013-05-01 19:23:04 rendon

谢谢我会自己尝试，如果有任何问题，我会来找你。 – shahwarcoder 2013-05-02 20:01:58

动态编程MPILOT

回答

相关问题