luoguP1007 独木桥题解

标题传送门
概括标题：

• \(n\)个士兵，要么不绝往左，否则不绝往右。
  
• 长度为\(m\)
  
• 若两个士兵同点，向右走的向左，向左走的向右。
  
• 恣意安排方向，问：
  
  
  
  • 1.最慢几秒
    
  • 2.最快几秒
    
  
  

标题一：

• 两个士兵同点，对答案有什么影响？
  

思索1：同点的碰撞有现实效果吗？

我们研究一下：

• 设两个士兵\(A\)，\(B\)，\(A\)从\(5\)至\(10\)，\(B\)从\(7\)至\(0\)。
  
• 不难发现，在点\(6\)，\(A\)，\(B\)同点。
  
• \(A\)已从\(5\)至\(6\)，\(B\)已从\(7\)至\(6\)
  
• \(A\) 向后转，走向左尽头，停:左尽头是\(B\)的尽头
  
• \(B\) 也向后转，走向右尽头，停:右尽头是\(A\)的尽头
  
• 不碰撞：\(A\)从\(6\)至\(10\)，\(B\)从\(6\)至\(0\)
  
• 碰撞：\(B\)从\(6\)至\(10\)，\(A\)从\(6\)至\(0\)
  
• 标题只关注时间，不关注是谁到的！
  

同点的碰撞无现实效果

简化标题：

• \(n\)个士兵，要么不绝往左，否则不绝往右。
  
• 长度为\(m\)
  
• 恣意安排方向，问：
  
  
  
  • 1.最慢几秒
    
  • 2.最快几秒
    
  
  

标题二：

• 怎么浪费时间，怎么节省时间？
  

思索2：\(t=s/v\)

• \(s\)士兵走的路
  
  
  
  • 向左走：
    
    
    
    • 从初始至左尽头
      
    • \(s=\)士兵位置\(-0=\)士兵位置
      
    
    
  • 向右走：
    
    
    
    • 从初始至右尽头
      
    • \(s=m+1-\)士兵位置
      
    
    
  
  
• \(v\)在题中为\(1\)
  
• \(\max(t)=\max(\text{士兵位置}~,~m+1-\text{士兵位置})\)
  

代码:

[code]#includeusing namespace std;int a[5011],l,n,ma=0,mi=0;int main(){        cin>>l>>n;        for(int i=1;i>a;                ma=max(ma,max(l+1-a,a));                mi=max(mi,min(l+1-a,a));        }        cout