I 安装饮水机中国石油大学新生训练赛#10

问题 I: 安装饮水机

时间限制: 1 Sec 内存限制: 128 MB
提交状态

题目描述

为倡导城市低碳生活，市文明办计划举办马拉松比赛，为确保比赛安全，沿途设置了一些观察点。每个观察点派一个观察员驻守。由于天气比较炎热，需要在沿途安装一些饮水机，使得观察员可以去取水喝。由于观察员每移动一个单位的路程，需要耗费一个单位的体力。而每个观察员的体力有限，只能在他体力能支持的范围内去取水喝，要不他就会渴死或累死。
聪明的楠楠也参与了这次比赛的筹备工作。他的任务是设计一个理想的安装饮水机方案，使得安装的饮水机最少，但又保证所有观察员都能取到水喝。

输入

输入数据有若干行。。
第一行，仅一个整数，表示有N(0<n<=1000)个观察点。
接下来有N行，每行两个整数S(0<S<=100000)和W(0<W<=50000)，其中S表示某个观察点到起点的路程，W表示该观察点中驻点观察员的体力。

输出

输出最少要安装几台饮水机。

样例输入 Copy

样例输出 Copy

提示

他可以将饮水机安装在距离起点为6和12的位置上，这样所有的观察员都能喝到水。方案有多种，只需输出最少需要几台饮水机即可。

思路：

他的任务是设计一个理想的安装饮水机方案，使得安装的饮水机最少，但又保证所有观察员都能取到水喝。

并且载体是一个直线正整数数轴，很难不想到用二分答案的方法来解决问题。

二分的是饮水机的数目，寻找的特殊状态是最小值。选用直接返回答案的二分模板：

    int l = 0, r = n;

    while(l < r)

    {

        int mid = l + r >> 1;

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

        else r = mid;

    }

    cout<<l;

输入数据中每个数据有两个相关数据，而且都和每个点有关，所以考虑创建结构体进行计算与输入。

之后就要写check函数，首先考虑便是按其位置从小到大排序，然后贪心，遍历每一个元素，如果当前最近饮水机位置在范围内则跳过，反之则放在当前元素的最右端（由于是按位置排序）

但是这种贪心+排序的做法并没法ac，举一组hack数据:

这组数据如果按照上述贪心进行遍历的话，第一个饮水机位置就会更新在10000这个点然后第二个会放在3这个点实际上只需要放在3这个点就可以满足所有的需要

因此需要换一种贪心方式，观察这组hack数据，可以发现，如果按a[i] + b[i]进行由小到大的排序，便可以贪心的跑完每一种情况

所以输入数据后，将结构体数组按a[i] + b[i]由小到大排序，可以通过重写sort实现。

记得初始化饮水机位置为0x3f3f3f3f（足够大就行）

代码： 2021.12.3

/*

************************************

***********emu^w^***********

*/

#include <bits/stdc++.h>

using namespace std;

#define x first

#define y second

const int P = 13131;

#define ll long long

const int mod = 1E6 + 7;

const int INF = 0x3f, sINF = 0x3f3f3f3f;

typedef unsigned long long ULL;

typedef pair<int, int> PII;

typedef pair<long long, long long> PLL;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

//

const int N = 1010;

int n;

struct answ{

    int a, b;

}q[N]; 

bool cmp(const answ &x, const answ &y)

{

    if(x.a + x.b != y.a + y.b) return x.a + x.b < y.a + y.b;

    return x.a < y.a;

}

bool check(int x)

{

    int nums = x;

    int loc = 0x3f3f3f3f;

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

    {

        if(loc > q[i].a + q[i].b || loc < q[i].a - q[i].b) {

            nums--;

            loc = q[i].a + q[i].b;

        }

        if(nums < 0) return true;

    }

    return false;

}

int main()

{

    cin>>n;

    for(int i = 1; i <= n; i++) cin>>q[i].a>>q[i].b;

    sort(q + 1, q + 1 + n, cmp);

    int l = 0, r = n;

    while(l < r)

    {

        int mid = l + r >> 1;

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

        else r = mid;

    }

    cout<<l;

}

巴特西

I 安装饮水机中国石油大学新生训练赛#10

问题 I: 安装饮水机

题目描述

输入

输出

样例输入 Copy

样例输出 Copy

提示

最新文章

热门文章

巴特西

I 安装饮水机 中国石油大学新生训练赛#10

问题 I: 安装饮水机

题目描述

输入

输出

样例输入 Copy

样例输出 Copy

提示

最新文章

热门文章

I 安装饮水机中国石油大学新生训练赛#10