题目描述 为倡导城市低碳生活，市文明办计划举办马拉松比赛，为确保比赛安全，沿途设置了一些观察点。每个观察点派一个观察员驻守。由于天气比较炎热，需要在沿途安装一些饮水机，使得观察员可以去取水喝。由于观察员每移动一个单位的路程，需要耗费一个单位的体力。而每个观察员的体力有限，只能在他体力能支持的范围内去取水喝，要不他就会渴死或累死。
聪明的楠楠也参与了这次比赛的筹备工作。他的任务是设计一个理想的安装饮水机方案，使得安装的饮水机最少，但又保证所有观察员都能取到水喝。 输入格式 输入数据有若干行。
第一行，仅一个整数，表示有N个观察点。
接下来有N行，每行两个整数Si和Wi，其中表示每个观察点到起点的路程，表示该观察点中驻点观察员的体力。 输出格式 输出最少要安装几台饮水机。 样例 样例输入
4 6 3 12 2 1 5 14 5 样例输出 2 题解 这道题跟种树差不多,就是加了一个特判p[i].n<0时等于零；
#include <bits/stdc++.h> using namespace std; struct st{ int n,m,k; }p[500005]; bool cmp(st x,st y){ return x.m<y.m; } int a, b, s[500005] = {}, ans; int main() { scanf("%d", &b); for (int i = 1; i <= b; i++) { scanf("%d%d", &p[i].n, &p[i].m); p[i].n=p[i].n-p[i].m; p[i].m=p[i].n+2*p[i].m; p[i].n=max(p[i].n,0); p[i].k=1; } sort(p+1,p+b+1,cmp); for (int i = 1; i <= b; i++) { for (int j = p[i].n; j <= p[i].m; j++) { if (p[i].k == 0) { break; } if (s[j] == 1) { p[i].k--; } } for (int j = p[i].m; j >= p[i].n; j--) { if (p[i].k == 0) { break; } if (s[j] == 0) { p[i].k--; s[j] = 1; ans++; } } } printf("%d", ans); return 0; }