支援救灾

支援救灾2008年5月12日14时28分,四川省发生强烈地震,震中位于阿坝州汶川县,地震造成了严重的生命和财产损失。中国人民解放军某部接上级命令,组织部分官兵,携带重要的救灾物品,尽快赶往灾区支援救灾。第一批赶赴灾区的官兵共有N人,每人都要先到军备库领取需携带的救灾物品,然后整装打包,再整队集合发出。现在每名官兵已拿到各自要携带的物品清单,由于清单内容不同,他们在军备库领取物品所需的时间也不同,整装打包的时间也不同。军备库有两名管理员负责发放物品,为了能够尽快整队出发,官兵们将排成两条队伍,分别在两名管理员处领取物品。每名官兵在领到物品后,马上整装打包,打完包后马上到指定地点集合。已知每名官兵领取物品和整装打包的时间,请你安排一种最佳的分队和排队方案,使得部队能够尽快出发支援救灾。【输入】从键盘输入数据。第一行为正整数R(R<=10),表示以下共有R组数据。然后分别是R组数据。每组数据的第一行为正整数N(0<N<=200),以下有N行,每行两个正整数Ai和Bi(0<Ai, Bi<=200),分别代表第i名官兵领取物品和打包的时间。【输出】对于每组数据,单独一行输出一个整数T,代表从领取物品开始到所有官兵打包结束可整队集合的最短时间。 样例: 样例输入 样例输出 2 2 1 3 3 2 5 2 2 7 7 1 3 6 4 8 5 5 17

样例输入 样例输出 2 2 1 3 3 2 5 2 2 7 7 1 3 6 4 8 5 5 17 第二组数据的一种最佳方案如下:

队伍1 队伍2 7 7 6 4 2 2 1 3 8 5 #include <iostream> #include <algorithm> #include <utility> #include <map> using namespace std; struct AB { int a, b;   // 领取物品和整理打包时间  bool operator < (const AB &r) const // 用于排序 {    return b > r.b; } }; int main() { int R;    // 数据组数  cin >> R; for (int i = 0; i < R; i++)   {       int N;   // 官兵人数      AB data[200]; // A、B数据       cin >> N;       for (int j = 0; j < N; j++)      cin >> data[j].a >> data[j].b;    sort(data, data + N);   // 按b排序     map<int, int> Que;   // <当前领取时间,两条队伍的最长完成时间>     Que[data[0].a] = data[0].a + data[0].b; // 分配第一个人入队       int totalA = data[0].a;     // 当前总的领物品时间       //Que[data[0].second] = Que[0];     for (int j = 1; j < N; j++) // 逐个分配到不同队伍中     {     map<int, int> newQue; // 新的队伍状态     for (map<int, int>::iterator it = Que.begin(); it != Que.end(); ++it)     // 对于当前所有可能的不同队伍状态      {      // 方案一:加入Que中       int oldTA = it->first;    // 当前队伍领取物品总时间      int oldSumTime = it->second; // 当前两条队伍的最长完成时间      int newSumTime = oldTA + data[j].a + data[j].b; // 新加入者的完成时间      if (newSumTime < oldSumTime)      newSumTime = oldSumTime; // 新的最长完成时间       // 要计算相同状态的最优值,即相同领取物品时间下的最短完成时间      map<int, int>::iterator it2 = newQue.find(oldTA + data[j].a);      if (it2 == newQue.end() || it2->second > newSumTime) // 无值或原值较大       newQue[oldTA + data[j].a] = newSumTime;   // 更新     // 方案二:加入另一队伍中      oldTA = totalA – it->first;   //当前队伍领取物品总时间可计算得到      newSumTime = oldTA + data[j].a + data[j].b;      if (newSumTime < oldSumTime)          newSumTime = oldSumTime;       it2 = newQue.find(it->first);       if (it2 == newQue.end() || it2->second > newSumTime)       newQue[it->first] = newSumTime;     }     // 准备下一次循环     totalA += data[j].a;

         // 更新总的领物品时间    

Que.swap(newQue);     // 更新队伍状态   

}    int minTime = 200 * 200;    for (map<int, int>::iterator it = Que.begin(); it != Que.end(); ++it)     if (it->second < minTime)    minTime = it->second;   cout << minTime << endl; }    return 0; }

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>