百度笔度题-----蚂蚁爬杆问题

从网上搜了一道:

/*
题目描述:
/*百度面试题
* 有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
* 木杆很细,不能同时通过一只蚂蚁。开始 时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,
* 但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。
* 编写程序,求所有蚂蚁都离开木杆 的最小时间和最大时间。
*/
#include
<iostream>
#include
<algorithm>
using namespace std;
//蚂蚁移动的方向,1为向右,-1为向左
int direction[5]={-1,-1,1,-1,1};
float f(){
    
int temp_dir[5];
    copy(direction,direction
+5,temp_dir);
    
float time=0;
    
int remains=5;
    
float pos[5]={3,7,11,17,23};
    
int start=0;
    
int end=4;
    
while(remains>0){
        time
+=0.5;
        
for(int i=start;i<=end;i++){
            pos[i]
+=direction[i]*0.5;
        }
        
for(int i=start;i<=end-1;i++){
            
if(pos[i]==pos[i+1]){
                temp_dir[i]
=-temp_dir[i];
                temp_dir[i
+1]=-temp_dir[i+1];
            }
        }
        
if(pos[start]<=0||pos[start]>=27){
            start
++;
            remains
--;
        }
        
if(pos[end]<0||pos[end]>27){
            end
--;
            remains
--;
        }
    }
    //cout
<<time;
    
return time;
}
float _min=1000;
float _max=-1;
int min_dir[5];
int max_dir[5];
void cal(int i){
    
if(i==5){
        
float result=f();
        
if(result<_min){
            _min
=result;
            copy(direction,direction
+5,min_dir);
        }
        
if(result>_max){
            _max
=result;
            copy(direction,direction
+5,max_dir);
        }
        
return;
    }
else{
        direction[i]
=-1;
        cal(i
+1);
        direction[i]
=1;
        cal(i
+1);
    }
}
int main(){
    cal(
0);
    cout
<<"min:"<<_min<<endl<<"max:"<<_max<<endl;
    ostream_iterator
<int> os(cout," ");
    copy(max_dir,max_dir
+5,os);
    cout
<<endl;
}
运行结果:
min:11
max:24.5
max的方向为:
向右 向左 向左 向左 向左
小人本潜水在思源的贴边
ID又多 又有钱
快活乐无边
谁知道站总监
他蛮横不留情面
他勾结站长目无天
占我ID夺我钱
我马甲跟他来翻脸
反被他来把经验减
我同学骂他欺新人
反被他捉进了小黑屋里面
874了一百遍啊一百遍
啊 最后他咬舌自尽 遗恨人间
他还将我和马甲赶出了思源 流落在人间
我为求回思源
无奈行乞在贴前
谁知道站总监他实在太阴险
知道此情形竟派人来暗算将我发文狂删到0篇
小人ID强 残命独留全
可怜马甲他 竟遭删
为求养ID
惟有傍人卖身自作践
一面苦赚钱 一面写诗篇
发誓把名气显
手刃总监意志坚啊
从此总监ID念心间
我永铭记此仇不供戴天
原文地址:https://www.cnblogs.com/CUCmehp/p/1496061.html