【洛谷】【二分答案+贪心】P1316 丢瓶盖

【题目描述：】

陶陶是个贪玩的孩子，他在地上丢了A个瓶盖，为了简化问题，我们可以当作这A个瓶盖丢在一条直线上，现在他想从这些瓶盖里找出B个，使得距离最近的2个距离最大，他想知道，最大可以到多少呢？

【输入格式：】

第一行，两个整数，A,B。（B<=A<=100000）

第二行，A个整数，分别为这A个瓶盖坐标。

【输出格式：】

仅一个整数，为所求答案。

【算法分析：】

关于单调性的感性证明：

　　如果一个mid作为最大值时所选的瓶盖数量 x≥B，即最大值过小导致选取瓶盖过多，

　　则答案一定在[mid + 1, r]内

　　否则答案在[l, mid]内

满足单调性，可以二分答案。

关于check函数：

在check一个数mid时，check函数返回mid作为最大值时的选取瓶盖数量，

　　这里可以做一个优化，即check返回一个bool类型

　　当选取的瓶盖数量超过读入的B时，直接返回1，表示二分[mid + 1, r]这个区间

将数据从小到大排序来实现check函数：

　　读入有n个元素的序列a，最大值为max

　　利用贪心的思想，由于是求最少选取的瓶盖数量，能不选这个瓶盖的时候就不选

　　last表示上一次选取的瓶盖位置

　　当且仅当 a_i - last > max 时，不选取a_i会导致最大值变大，last更新成ai，选取的瓶盖个数+ 1

关于上下界的初始化：

　　二分时上下界的初始选择可以是[0, INF]，最多进行31次查找。

　　只选取两个瓶盖时的最大值为a_max- a_min ，由于数据已经排好序，上界直接初始化成 a_n - a₁ 即可

【代码：】

 //丢瓶盖

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int MAXN =  + ;

 const int INF = 0x7fffffff;

 int n, m;

 int a[MAXN];

 bool check(int num) {

     int ret = , last = a[];

     for(int i = ; i <= n; i++) {

         if(a[i] - last > num) last = a[i], ret++;

         if(ret >= m) return true;

     }

     return ret >= m;

 }

 int main() {

     scanf("%d%d", &n, &m);

     int l = , r = INF;

     for(int i = ; i <= n; i++) {

         scanf("%d", &a[i]);

     }

     sort(a + , a + n + );

     r = a[n] - a[];

     while(l < r) {

         int mid = (l + r) >> ;

         if(check(mid)) l = mid + ;

         else r = mid;

     }

     printf("%d\n", l);

 }

巴特西

【洛谷】【二分答案+贪心】P1316 丢瓶盖

最新文章

热门文章