Distinct

題目大意：

有n個軍隊（有自己在x軸上的坐標），每個軍隊有一定的人，要一個坐標只有一個人，移動路程最大的士兵最少移動多長

原題：

題目描述

Daniel 正在玩一個戰棋游戲。
現在 Daniel 有 n 隊士兵站在 x 軸上。第 i 隊士兵有 ai 人，坐標為 xi。
Daniel 看到一隊士兵有這么多人，都站在同一個位置，他對此很不滿意。他
想命令一些士兵移動到新的位置（必須是整點），使得不存在兩個士兵站在同一個
位置。
為了節約時間，Daniel 希望每個士兵的移動距離的最大值盡可能小。請求出
這個最小值。
輸入
第一行一個正整數 n，表示 Daniel 有多少隊士兵。第二行 n 個正整數 ai，表示每隊士兵的人數。第三行 n 個嚴格遞增的 整數 xi，表示每隊士兵的坐標。

輸出

一行一個非負整數，表示每個士兵的移動距離的最大值的最小值

輸入樣例

2 2 3 0 2

輸出樣例

1

說明

樣例解釋

移動后，5 個士兵的坐標分別為 -1, 0, 1, 2, 3。
有 2 個士兵移動距離為 0，3 個士兵移動距離為 1，因此答案是1

解題思路：

先二分答案，然后判斷
判斷：每個士兵盡量往左，然后判斷是否超過當前軍隊往右可以到的位置

代碼：

#include<cstdio> #define max(a,b) ((a)>(b)?(a):(b)) using namespace std; int n,l,r,q,mid,a[100005],x[100005]; bool check(int dep) {q=x[1]-dep+a[1];//盡量往左if (q-1>x[1]+dep) return false;//因為p是下一支隊的開始，所以要-1for (int i=2;i<=n;++i){q=max(q,x[i]-dep)+a[i];//如果有交差就要從上一支隊開始if (q-1>x[i]+dep) return false;//判斷是否超過}return true; } int main() {scanf("%d",&n);for (int i=1;i<=n;++i){scanf("%d",&a[i]);l=max(l,a[i]);//最小r+=a[i]; //最大}for (int i=1;i<=n;++i)scanf("%d",&x[i]);l/=2;while (l<=r)//二分{mid=(l+r)/2;if (check(mid)) r=mid-1;else l=mid+1;}printf("%d",l); }

總結

以上是生活随笔為你收集整理的【二分】Distinct的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。