博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
九度 1554:区间问题
阅读量:5847 次
发布时间:2019-06-18

本文共 2212 字,大约阅读时间需要 7 分钟。

题目描述:

给定一个数组,判断数组内是否存在一个连续区间,使其和恰好等于给定整数k。

 

输入:

输入包含多组测试用例,每组测试用例由一个整数n(1<=n<=10000)开头,代表数组的大小。

接下去一行为n个整数,描述这个数组,整数绝对值不大于100。
最后一行为一个整数k(大小在int范围内)。

 

输出:

对于每组测试用例,若存在这个连续区间,输出其开始和结束的位置,s,e(s <= e)。

若存在多个符合条件的输出,则输出s较小的那个,若仍然存在多个,输出e较小的那个。
若不存在,直接输出"No"。

 

样例输入:
5-1 2 3 -4 953-1 2 -372-1 10
样例输出:
2 3No1 2

思路

1. o(n^n) 复杂度算法超时

2. 正解. D[i] 记录 0~i 的和, 若 D[j] - D[i] == k, 那么 i~j 是一个可行解. 对 D[i] 进行索引排序后枚举 i 并使用二分查找 j. 时间复杂度为 o(nlogn)

 

代码 未通过九度测试

#include 
#include
#include
using namespace std;class Node {public: int i, di; Node(int _i, int _di):i(_i), di(_di) { } Node() { Node(0, 0); } bool operator<(const Node &ths) const { if(this->di == ths.di) return this->i < ths.i; return this->di < ths.di; }};int d[10010];int arr[10010];Node nodes[10010];int st, ed;int binary_search(int low, int high, int target, int &left, int &right) { int low1 = low, high1 = high; // find the left part of array while(low1 <= high1) { int mid = (low1+high1)>>1; if(nodes[mid].di < target) { low1 = mid + 1; }else{ high1 = mid -1; } } left = low1; low1 = low, high1 = high; while(low1 <= high1) { int mid = (low1+high1)>>1; if(nodes[mid].di <= target) { low1 = mid + 1; }else{ high1 = mid -1; } } right = high1; if(left < low || right > high || nodes[left].di != target) return -1; return 0;}int main() { freopen("testcase.txt", "r", stdin); int n, k; while(scanf("%d", &n) != EOF) { scanf("%d", arr); nodes[0].i = 0; nodes[0].di = arr[0]; d[0] = arr[0]; for(int i = 1; i < n; i ++) { scanf("%d", arr+i); d[i] = d[i-1]+arr[i]; nodes[i].i = i; nodes[i].di = d[i]; } scanf("%d", &k); sort(nodes, nodes+n); int minst = 0, mined = 0x3f3f3f3f; for(int i = 0; i < n; i ++) { int target; if(i == 0) { target = k; }else{ target = d[i-1] + k; } int left, right; if(binary_search(0, n-1, target, left, right) == -1) { // didn't find continue; }else { for(int j = left; j <= right; j ++) { int index = nodes[j].i; if(index < i) continue; minst = i; mined = index; break; } break; } } if(mined != 0x3f3f3f3f) printf("%d %d\n",minst+1, mined+1 ); else printf("No\n"); } return 0;}

  

转载地址:http://sbwjx.baihongyu.com/

你可能感兴趣的文章
大数据公司Palantir融得7亿美元 曾追踪拉登
查看>>
建立备份策略的重要性
查看>>
发力IoT领域 Marvell注重生态系统发展
查看>>
你应该知道的 RPC 原理
查看>>
Ubuntu安装词典
查看>>
Spring解析
查看>>
python中str和repr区别
查看>>
数据挖掘-同比与环比
查看>>
RedHat6 管理应用服务【11】
查看>>
stm32F10x复习-1
查看>>
[转] vue异步处理错误
查看>>
CSS 3D动画概述菜鸟级解读之一
查看>>
kindeditor.net应用
查看>>
函数preg_replace()与str_replace()
查看>>
HTTP工具CURL的使用简介
查看>>
P2P的远程协助系统技术分析[转]
查看>>
在.NET开发中的单元测试工具之(1)——NUnit
查看>>
windows2008支持多用户同时登录
查看>>
UEditor 1.2.5 for java 自定义配置
查看>>
从Redis的数据丢失说起
查看>>