SGU 531 - Bonnie and Clyde 预处理+二分
Bonnie and Clyde
Description
Bonnie and Clyde are into robbing banks. This time their target is a town called Castle Rock. There are n banks located along Castle Rock's main street; each bank is described by two positive integers xi, wi, where xi represents the distance between the i-th bank and the beginning of the street and wi represents how much money the i-th bank has. The street can be represented as a straight line segment, that's why values of xi can be regarded as the banks' coordinates on some imaginary coordinate axis.
This time Bonnie and Clyde decided to split, they decided to rob two different banks at a time. As robberies aren't exactly rare in Castle Rock, Bonnie and Clyde hope that the police won't see the connection between the two robberies. To decrease the chance of their plan being discovered by the investigation, they decided that the distance between the two robbed banks should be no less than d.
Help Bonnie and Clyde find two such banks, the distance between which is no less than d and the sum of money in which is maximum.
Input
The first input line contains a pair of integers n, d (1 ≤ n ≤ 2 · 105, 1 ≤ d ≤ 108), where n is the number of banks and d is the minimum acceptable distance between the robberies. Then n lines contain descriptions of banks, one per line. Each line contains two integers xi, wi (1 ≤ xi,wi ≤ 108), xi shows how far the i-th bank is from the beginning of the street and wi shows the number of money in the bank. Positions of no two banks coincide. The banks are given in the increasing order of xi.
Output
Print two integer numbers — indicies of the required banks. The banks are numbered starting from 1 in the order in which they follow in the input data. You may print indicies in any order. If there are many solutions, print any of them. If no such pair of banks exists, print "-1 -1" (without quotes).
Sample Input
6 3
1 1
3 5
4 8
6 4
10 3
11 2
Sample Output
5 3
题意
给你n个银行,每次银行的位置x[i],金钱w[i], 现在让你选择两个不同的银行 使其距离大于等于D 且金钱和最大
输出选择的那两个银行,序号
题解:
我是先预处理出 i ~n 中 金钱最多的,序号是那个
再遍历一次, 二分当前x[i]+ d的 序号就好了, 即 与其距离满足大于等于d且 金钱最多的是哪一个银行 ,更新答案
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long ll; const int N = + ;
const ll inf = ; ll x[N], w[N], M[N], H[N],n,d;
void init() {
M[n+] = -;
H[n + ] = n+;
for(int i = n; i >= ; i--) {
if(w[i] >= M[i + ]) M[i] = w[i], H[i] = i;
else M[i] = M[i+], H[i] = H[i + ];
// cout<<M[i]<<" "<<H[i]<<endl;
}
}
int main() {
scanf("%I64d%I64d",&n,&d);
for(int i = ; i <= n; i++) {
scanf("%I64d%I64d",&x[i],&w[i]);
}
x[n + ] = inf; w[n + ] = -inf;
init();
ll ans = , ansl = -, ansr = -;
for(int i = ; i <= n; i++) {
ll tmp = x[i] + d;
int pos = lower_bound(x + , x + n + , tmp) - x;
if(pos == n + ) break;
if(w[i] + w[H[pos]] > ans ) ans = w[i] + w[H[pos]], ansl = i, ansr = H[pos];
}
printf("%I64d %I64d\n",ansl,ansr);
return ;
}
代码
最新文章
- Android Studio-—使用OpenCV的配置方法和demo以及开发过程中遇到的问题解决
- ThinkPHP 3.2 获取页面运行时间
- Android基于mAppWidget实现手绘地图(六)–如何展示地图对象
- 【Android】Fragment的简单笔记
- netbeans中给jpanl添加背景图片制定代码的理解——匿名内部类继承父类
- C语言 指针与字符串
- ubuntu下设置开机自动挂载硬盘
- [译] 所有你需要知道的关于完全理解 Node.js 事件循环及其度量
- for循环 例子
- PY3 多组输入
- JVM内存区域划分Eden Space、Survivor Space、Tenured Gen,Perm Gen解释 (生动形象)
- Appium 服务关键字(转)
- canvas相关api
- hadoop集群运行dedup实现去重功能
- 由浅入深之Tensorflow(2)----logic_regression实现
- 网站 安全 ---- 常见的 web 攻击
- PHP中不用第三个变量交换两个变量的值
- IO流框架关系总结(关系图)
- google浏览器:Ignored call to &#39;confirm()&#39;. The document is sandboxed, and the &#39;allow-modals&#39; keyword is not set
- 申请社交平台appkey详细教程