f******s
发帖数: 96 | 1 这个问题可能大家听说过，能否generalize一下给出算法。
一批人要从A岸到B岸，天黑要手电，只有一把，最多可照明供两个人同时过河，目标是
所有人在最短的时间内过河。
假设现有4个人，过河分别需要1.3.6.10分钟，那么最快需要多长时间全部过河？
解答：
1、3过河，1返回，6、10过河，3返回，1、3过河，总时间3+1+10+3+3=20.
现在generalize一下，假设有100个人要过河，速度大都不同，有没有general的算法？ | a**********s
发帖数: 588 | 2 void GuoHe(const vector& A)
{
sort(A.begin(), A.end());
const People& first = A[0];
const People& second = A[1];
Guohe(first, second);
Return(first);
int i = A.size()-1;
while (i > 2) {
const People& P0 = A[i];
const People& P1 = A[i];
GuoHe(P0, P1);
Return(second);
Guohe(first, second);
Return(first);
i -= 2;
}
if (i == 2)
Guohe(first, A[i]);
else
Guohe(first);
} | a**********s
发帖数: 588 | | p*********a
发帖数: 21 | 4 呵呵, 这个心贪的有些过, 试试这组数据
1 7 8 20
【在 a**********s 的大作中提到】
: void GuoHe(const vector& A)
: {
: sort(A.begin(), A.end());
: const People& first = A[0];
: const People& second = A[1];
: Guohe(first, second);
: Return(first);
: int i = A.size()-1;
: while (i > 2) {
: const People& P0 = A[i];
| a********a
发帖数: 219 | 5 可惜这个id了。
【在 a**********s 的大作中提到】
: void GuoHe(const vector& A)
: {
: sort(A.begin(), A.end());
: const People& first = A[0];
: const People& second = A[1];
: Guohe(first, second);
: Return(first);
: int i = A.size()-1;
: while (i > 2) {
: const People& P0 = A[i];
| b***e
发帖数: 1419 | 6 For this you just need to transport 2 people each time in a group, starting
from the slowest to the fastest. For each group, you either do:
1,2
1,
3,4
2,
Or do:
1,4,
1,
1,3,
1
which ever is faster. | a********a
发帖数: 219 | 7 再说一遍，greedy不work.
这个题明显不是greedy，如果第一眼看不出不是，那么就毫无疑问为什么还要来这个版
了。
starting
【在 b***e 的大作中提到】
: For this you just need to transport 2 people each time in a group, starting
: from the slowest to the fastest. For each group, you either do:
: 1,2
: 1,
: 3,4
: 2,
: Or do:
: 1,4,
: 1,
: 1,3,
| p*********a
发帖数: 21 | 8 呵呵, 这题明显是贪心~
三个人一下的情况就不讨论了, 三个人以上, 先排序, d[0], d[1]....d[n-2], d[n-1]
; 每次把速度最慢的两个人d[n-1], d[n-2]弄过去, 分两种情况讨论就可以了, 2*d[1]
<=d[0]+d[n-2] or 2*d[1]>d[0]+d[n-2]
【在 a********a 的大作中提到】
: 再说一遍，greedy不work.
: 这个题明显不是greedy，如果第一眼看不出不是，那么就毫无疑问为什么还要来这个版
: 了。
:
: starting
| b***e
发帖数: 1419 | 9 给个证明。
【在 a********a 的大作中提到】
: 再说一遍，greedy不work.
: 这个题明显不是greedy，如果第一眼看不出不是，那么就毫无疑问为什么还要来这个版
: 了。
:
: starting
| a**********s
发帖数: 588 | 10 解释一下, 举一个反例就好. 虽然你说话尖酸刻薄, 但是还是盼望不吝赐教...
【在 a********a 的大作中提到】
: 再说一遍，greedy不work.
: 这个题明显不是greedy，如果第一眼看不出不是，那么就毫无疑问为什么还要来这个版
: 了。
:
: starting
| | | a**********s
发帖数: 588 | 11 嗯, 我原先没有想清楚这一点
1]
1]
【在 p*********a 的大作中提到】
: 呵呵, 这题明显是贪心~
: 三个人一下的情况就不讨论了, 三个人以上, 先排序, d[0], d[1]....d[n-2], d[n-1]
: ; 每次把速度最慢的两个人d[n-1], d[n-2]弄过去, 分两种情况讨论就可以了, 2*d[1]
: <=d[0]+d[n-2] or 2*d[1]>d[0]+d[n-2]
| a********a
发帖数: 219 | 12 我没兴趣给一边骂我，一边问我的人解释。自己好好看算法书吧。或者google一下。
【在 a**********s 的大作中提到】
: 解释一下, 举一个反例就好. 虽然你说话尖酸刻薄, 但是还是盼望不吝赐教...
| p*********a
发帖数: 21 | 13 呵呵, 仅代表俺们这些第一眼看出这题明显是greedy的菜鸟们向看了不知多少眼还没有
看出这题是贪心的牛人赐教~
BTW, 能推荐几本讲greedy的算法么? google是什么, 不会用~ 可以顺便指导一下么?
【在 a********a 的大作中提到】
: 我没兴趣给一边骂我，一边问我的人解释。自己好好看算法书吧。或者google一下。
| a********a
发帖数: 219 | 14 我说话虽然难听，但我不刻薄，也不做作。我只说事实。
当人们为自己在言语上占了上风而得意的时候，有多少人会想到除了言语上的快感他其
实并没有得到任何东西呢？
随便说一句吧。Greedy第一原则：
If you cannot prove your greedy is correct, it is wrong.
【在 p*********a 的大作中提到】
: 呵呵, 仅代表俺们这些第一眼看出这题明显是greedy的菜鸟们向看了不知多少眼还没有
: 看出这题是贪心的牛人赐教~
: BTW, 能推荐几本讲greedy的算法么? google是什么, 不会用~ 可以顺便指导一下么?
| a**********s
发帖数: 588 | 15 "如果第一眼看不出不是，那么就毫无疑问为什么还要来这个版"
人在最痛苦的时候给人丢出这种话, 居然还不刻薄... 最要命的是自己水平明明很有限
【在 a********a 的大作中提到】
: 我说话虽然难听，但我不刻薄，也不做作。我只说事实。
: 当人们为自己在言语上占了上风而得意的时候，有多少人会想到除了言语上的快感他其
: 实并没有得到任何东西呢？
: 随便说一句吧。Greedy第一原则：
: If you cannot prove your greedy is correct, it is wrong.
| p*********a
发帖数: 21 | 16 hehe, 继续向除了得到言语上的快感, 又中了大奖的不刻薄，不做作, 只说事实好同志
请教这题greedy不work的证明, 也许证明太长, 我等看不懂, 给我们个reference也行,
让我们慢慢研究研究, 要不举个反例证明我下面的贪心程序不对的也可以
#include
#include
using namespace std;
const int N = 1000;
int n, d[N];
inline void solve() {
sort(d, d+n);
int tot = 0;
while(n>3) {
if(2*d[1]<=d[0]+d[n-2]) tot += d[0] + 2*d[1] + d[n-1];
else tot += 2*d[0] + d[n-1] + d[n-2];
n -= 2;
}
if(n==1) tot += d[0];
else if(n==2) tot += d[1];
else t
【在 a********a 的大作中提到】
: 我说话虽然难听，但我不刻薄，也不做作。我只说事实。
: 当人们为自己在言语上占了上风而得意的时候，有多少人会想到除了言语上的快感他其
: 实并没有得到任何东西呢？
: 随便说一句吧。Greedy第一原则：
: If you cannot prove your greedy is correct, it is wrong.
| a**********s
发帖数: 588 | 17 one counter example is enough.
But it is provable that the greedy algorithm would work | b***e
发帖数: 1419 | 18 You are mixing up provability with tautology. A statement cannot be
proved does not mean it is proved to be wrong. As an instance, you cannot
prove greedy works does not imply that you can disprove greedy works.
【在 a********a 的大作中提到】
: 我说话虽然难听，但我不刻薄，也不做作。我只说事实。
: 当人们为自己在言语上占了上风而得意的时候，有多少人会想到除了言语上的快感他其
: 实并没有得到任何东西呢？
: 随便说一句吧。Greedy第一原则：
: If you cannot prove your greedy is correct, it is wrong.
| b***e
发帖数: 1419 | 19 This is just a natural phenomena: there are assholes in this world, and
that's where shit comes from.
【在 a**********s 的大作中提到】
: "如果第一眼看不出不是，那么就毫无疑问为什么还要来这个版"
: 人在最痛苦的时候给人丢出这种话, 居然还不刻薄... 最要命的是自己水平明明很有限
|
|
