Bridge

PC/UVa 题号:110403/10037 题目描述

分析:如果每次都让最快的人陪别人过桥,然后他再返回陪另一个人过桥,这是最佳方案吗?以sample输入为例:有4个人,过桥时间分别是:1 2 5 10。按前述策略的过桥方案为:
1 10
1
1 5
1
1 2
共19秒。但按照sample的过桥策略只要17秒:
1 2
1
5 10
2
1 2
该策略其实是:先让最快的2个人过桥,让最快的一个返回送手电,再让最慢的两个人过桥,让第二快的人返回送手电,最后2个人一起过桥。这是最佳方案吗?
如果把要过桥的人按照过桥时间从小到大排列得到数列:a1, a2, …, a(n-1), a(n)。那么第二种策略可以表述为:
a1 a2
a1
a(n-1) a(n)
a2
经这4步,在最快的2个人的协助下,最慢的2个人过了桥,共用时:a1+2a2+a(n)秒;然后,最快的两个人接着再协助还没有过河的人中最慢的两个人过河;最后,最快的2个人一起过河,或者(在最后还剩3个人的情况下):
a1 a3
a1
a1 a2
在第一种策略下,送最慢的2个人过河需要的时间:
a1 a(n-1)
a1
a1 a(n)
a1
经这4步,在最快的一个人的协助下,最慢的2个人过了桥,共用时:2a1+a(n-1)+a(n)秒。同样是送2个最慢的人过河,两种策略的时间差为:

delta = a1+2a2+a(n) – (2a1+a(n-1)+a(n)) = 2a2 – (a1 + a(n-1)) = (a2 – a1) – (a(n-1) – a2)

第二种策略只在delta小于0的情况下才优于第一种策略。另外我们注意到:如果有a(n-1)使得上面的delta不小于0,则对于a(n-2)直到a3,如果用这些值分别代替上式中的a(n-1),delta都不小于0;也就是说,这这些情况下,第一种策略都不逊于第二种策略。

仔细思考,根据数列的情况,交替运用这2种策略,即可快速过河。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

inline int cross(vector<vector<int> > & order, int fast, int slow = 0) {
  if (!slow) {
    order.push_back(vector<int>(1, fast));
    return fast;
  }
  vector<int> group(2);
  group[0] = fast;
  group[1] = slow;
  order.push_back(group);
  return slow;
}

int min_time(vector<int> & people, vector<vector<int> > & order) {
  if (people.size() == 1) {
    order.push_back(vector<int>(1, people[0]));
    return people[0];
  }
  sort(people.begin(), people.end());
  int t = 0;
  int p0 = people[0];
  int p1 = people[1];
  while (!people.empty()) {
    int size = people.size();
    if (size == 2) {
      t += cross(order, p0, p1);
      people.clear();
    }
    else if (size == 3) {
      t += cross(order, p0, people[2]);
      t += cross(order, p0);
      t += cross(order, p0, p1);
      people.clear();
    }
    else {
      if (p1 - p0 < people[size - 2] - p1) {
        t += cross(order, p0, p1);
        t += cross(order, p0);
        t += cross(order, people[size - 2], people.back());
        t += cross(order, p1);
        people.pop_back();
        people.pop_back();
      }
      else {
        t += cross(order, p0, people.back());
        t += cross(order, p0);
        people.pop_back();
      }
    }
  }
  return t;
}

int main() {
  int n_case = 0;
  cin >> n_case;
  for (int i = 0; i < n_case; i++) {
    int n = 0;
    cin >> n;
    vector<int> people(n);
    int j;
    for (j = 0; j < n; j++)
      cin >> people[j];
    vector<vector<int> > order;
    int t = min_time(people, order);
    if (i != 0)
      cout << endl;
    cout << t << endl;
    for (j = 0; j < order.size(); j++) {
      for (int k = 0; k < order[j].size(); k++) {
        if (k != 0)
          cout << ' ';
        cout << order[j][k];
      }
      cout << endl;
    }
  }
}

《Bridge》有1个想法

  1. Pingback: 目录 | 狂童

发表评论

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

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