Day8 - G - Bound Found ZOJ - 1964
Signals of most probably extra-terrestrial origin have been received and digitalized by The Aeronautic and Space Administration (that must be going through a defiant phase: "But I want to use feet, not meters!"). Each signal seems to come in two parts: a sequence of n integer values and a non-negative integer t. We'll not go into details, but researchers found out that a signal encodes two integer values. These can be found as the lower and upper bound of a subrange of the sequence whose absolute value of its sum is closest to t.
You are given the sequence of n integers and the non-negative target t. You are to find a non-empty range of the sequence (i.e. a continuous subsequence) and output its lower index l and its upper index u. The absolute value of the sum of the values of the sequence from the l-th to the u-th element (inclusive) must be at least as close to t as the absolute value of the sum of any other non-empty range.
Input
The input file contains several test cases. Each test case starts with two numbers n and k. Input is terminated by n = k = 0. Otherwise, 1 <= n <= 100000 and there follow n integers with absolute values <= 10000 which constitute the sequence. Then follow k queries for this sequence. Each query is a target t with 0 <= t <= 1000000000.
Output
For each query output 3 numbers on a line: some closest absolute sum and the lower and upper indices of some range where this absolute sum is achieved. Possible indices start with 1 and go up to n.
Sample Input
5 1
-10 -5 0 5 10
3
10 2
-9 8 -7 6 -5 4 -3 2 -1 0
5 11
15 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
15 100
0 0
Sample Output
5 4 4
5 2 8
9 1 1
15 1 15
15 1 15
思路:维护前缀和,排序后维护双指针取值,细节直接看代码
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long LL;
typedef pair<LL, LL> PLL; const int maxm = 1e5+; int n, k; LL C[maxm]; void add(int x, int val) {
for(; x <= n; x += lowbit(x))
C[x] += val;
} LL getsum(int x) {
LL ret = ;
for(; x; x -= lowbit(x))
ret += C[x];
return ret;
} struct Node {
LL val;
int id;
bool operator<(const Node &a) const {
return val < a.val;
}
} Nodes[maxm]; int main() {
ios::sync_with_stdio(false), cin.tie();
int t, val;
while(cin >> n >> k && n+k) {
memset(C, , sizeof(C));
for(int i = ; i <= n; ++i) {
cin >> val;
add(i, val);
Nodes[i] = {getsum(i), i};
}
Nodes[].id = , Nodes[].val = ;
sort(Nodes,Nodes++n);
while(k--) {
int l = , r = , ansL, ansR;
LL ans, t, diff = 0x3f3f3f3f;
cin >> t;
while(l <= n && r <= n) {
LL val = Nodes[r].val - Nodes[l].val;
if(abs(val - t) < diff) {
ans = val;
diff = abs(val-t);
ansL = min(Nodes[l].id+,Nodes[r].id+);
ansR = max(Nodes[l].id, Nodes[r].id);
}
if(val > t)
l++;
else if(val < t)
r++;
else break;
if(l == r) r++;
}
cout << ans << " " << ansL << " " << ansR << "\n";
} } return ;
}
最新文章
- 纯CSS完成tab实现5种不同切换对应内容效果
- Mysql 中有关日期的函数(sql)
- Entity Framework做IN查询
- hdu 5691 Sitting in Line 状压dp
- Android手机开机自动启动
- 如何在 Windows Azure 的虚拟机 ubuntu 上面安装和配置 openVPN(二)
- 数据库VIEW(视图)
- 【C++】关于pow函数的用法
- AMD与CMD区别
- java中队列Queue的使用
- Pymongo使用事项
- tensorflow笔记4:函数:tf.assign()、tf.assign_add()、tf.identity()、tf.control_dependencies()
- shell编程基础(七): 处理文件命令sed与awk
- 文件IO模型
- hbase 快速开发
- eclipse创建web项目web.xml配置文件笔记
- bzoj4176. Lucas的数论 杜教筛
- 二叉树的递归,非递归遍历(java)
- ubuntu wireshark找不到网卡及开启IP转发
- 如何使不同时区的时间与京8区一致?(JS实现)
热门文章
- solve License Key is legacy format when use ACTIVATION_CODE activate jetbrains-product 2019.3.1
- NGINX生命周期-转
- GitHub 网站汉化
- k种球若干,取n个球,输出所有取球方案 (模拟)
- Java基础 -2.6
- c++拷贝构造函数(翁恺c++公开课[26-27]学习笔记)
- 搭建python虚拟环境virtualenv
- 【转】android之在activity中控制另一个activity的UI更新_如何在activity之间传递handler
- 线程安全Collections.synchronizedList
- 设计模式课程 设计模式精讲 11-2 装饰者模式coding