餐饮行业网站建设风格,遵义市和城乡建设局网站,东莞金融网站建设,定制网站+域名+企业邮箱Distinct
题目大意#xff1a;
有n个军队#xff08;有自己在x轴上的坐标#xff09;#xff0c;每个军队有一定的人#xff0c;要一个坐标只有一个人#xff0c;移动路程最大的士兵最少移动多长
原题#xff1a;
题目描述
Daniel 正在玩一个战棋游戏。 现在 Danie…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 个士兵移动距离为 03 个士兵移动距离为 1因此答案是1
解题思路
先二分答案然后判断 判断每个士兵尽量往左然后判断是否超过当前军队往右可以到的位置
代码
#includecstdio
#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)
{qx[1]-depa[1];//尽量往左if (q-1x[1]dep) return false;//因为p是下一支队的开始所以要-1for (int i2;in;i){qmax(q,x[i]-dep)a[i];//如果有交差就要从上一支队开始if (q-1x[i]dep) return false;//判断是否超过}return true;
}
int main()
{scanf(%d,n);for (int i1;in;i){scanf(%d,a[i]);lmax(l,a[i]);//最小ra[i]; //最大}for (int i1;in;i)scanf(%d,x[i]);l/2;while (lr)//二分{mid(lr)/2;if (check(mid)) rmid-1;else lmid1;}printf(%d,l);
}
