分治思想求解,超时了分析了一下T(n)=O(n)+O(logn)*k(k可能渐进为n)
#include<iostream> #include<stdio.h> using namespace std; int cases,total,sum; const int maxm=100000; int array[maxm]; int enumFind(int*array,int start,int end) { int mid=(start+end)/2; for(int i=mid;i>=start;i--) { for(int j=mid+1;j<=end;j++) { int a=0; for(int k=i;k<=j;k++) { a+=array[k]; } if(a>=sum) { return j-i+1; } } } return 0; } int binaryFind(int* array,int start,int end) { if(start==end) { if(array[start]>=sum) return 1; else return 0; } else { int mid=(start+end)/2; int fore=binaryFind(array,start,mid); int behind=binaryFind(array,mid+1,end); int enu=0; int min=0; if(fore>0) min=fore; if(behind>0&&min==0) min=behind; if(behind>0&&min>0) { if(behind<min) min=behind; } if(fore==0&&behind==0) { enu=enumFind(array,start,end); } else { if(min>2) enu=enumFind(array,mid-min+3,mid+min-2); } if(min==0) min=enu; else { if(enu>0&&enu<min) min=enu; } return min; } } int main() { cin>>cases; while(cases--) { cin>>total>>sum; for(int i=0;i<total;i++) { //cin>>array[i]; scanf("%d",array+i); } cout<<binaryFind(array,0,total-1)<<endl; } return 0; }
网上找了个二分法,以搜索的连续字符长度为变量二分,AC了
#include <iostream> using namespace std; int sum[100001]; int main() { int repeat,i,m,s,x; int len,mid,high,low,flag; cin>>repeat; while(repeat--) { cin>>m>>s; sum[0]=0; for(i=1;i<=m;i++) { scanf("%d",&x); sum[i]=sum[i-1]+x; } low=1; high=m; len=0; while(low<=high) { mid=(low+high)/2; flag=0; for(i=mid;i<=m;i++) { if(sum[i]-sum[i-mid]>=s) { flag=1; len=mid; break; } } if(flag) high=mid-1; else low=mid+1; } cout<<len<<endl; } return 0; }
发表评论
-
图的割点tarjan---zoj_1119
2011-10-24 23:00 1242http://acm.zju.edu.cn/on ... -
BFS与双向BFS---zoj_1505
2011-10-09 17:14 1652http://acm.zju.edu.c ... -
静态treap+线段树---zoj_2112
2011-09-29 23:06 1720http://acm.zju.edu ... -
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
2011-09-23 23:00 1325Nim游戏是两个人进行的游戏有如下规则: ... -
多重背包--zoj_2156
2011-09-14 11:10 875首先介绍经典的三种背包问题,0-1背包,完全 ... -
模式串匹配---KMP
2011-08-31 20:49 1289朴素的的模式串匹配算法通常要在向前移动文本指针 ... -
八数码问题(A*&&双向BFS)---zoj_1217
2011-08-30 22:13 1677题目地址:http://acm.zju.edu.cn/onli ... -
ac自动机以及它上面的DFA
2011-08-08 23:04 2497AC自动机(Aho-Corasick)主要用 ... -
二分图最大匹配(匈牙利算法)--zoj1516,1525,2223
2011-07-20 22:36 1196二分图G(E,V)将点集合V分成两个部分L,R ... -
网络最大流(EK)---zoj_1734
2011-07-19 16:34 2144网络最大流是图论中的一个典型问题,为了精确的定 ... -
trie和前缀检查---zoj_2876
2011-07-13 23:03 873trie树是一种多叉树,广泛用于字典检索。如 ... -
位图bitmap
2011-07-13 21:08 924bitmap是一种广泛使用的数据结构,主要用在 ... -
LAC和RMQ的转化---zoj_3195
2011-07-12 22:35 1080我擦。。纠结了好久啊,从SF到TLE,先总结2 ... -
LAC的tarjan(离线)算法---zoj_1141
2011-07-08 17:52 1667LCA就不解释了,这里主要再次复习一下LC ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2853zoj_2243笛卡 ... -
线段染色,矩形切割,离散化---zoj_2301,zoj_1128
2011-06-24 22:32 1376染色问题:在一维坐标轴上(最右端为M),有N ... -
线段树---zoj_1610
2011-06-22 21:06 763线段树是一种二叉树的拓展,在线段树每个节点中 ... -
快速排序(qsort)
2011-06-16 17:03 783快速排序是一种高效的非稳定排序,它的基本思路 ... -
斐波那契散列
2011-06-16 16:38 3087斐波那契散列法其实是一种特殊的乘法散列,先来看乘法 ... -
强连通分支(scc)---tarjan
2011-06-15 16:17 1292本文大量 ...
相关推荐
最近在acm.zju.edu.cn上通过的题目的代码,都是比较有价值的题目
zoj吐血制作,希望大家喜欢
浙江大学ZOJ源码题解,按照题目类型和难易分类。
zoj在线评测系统前台和后台源代码,包括比赛用的客户端源代码
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
zoj4041正确题解源代码,以及运行程序
这是一份ZOJ的ACM题解,包含大多数题目的AC程序,是学习算法的好东西~
acm中zoj1002的可运行C++程序
一个非常非常非常非常实用的zoj结题代码
问题:枫教授在一所大学教数学,他发现了一个函数,用于获得一个表达式的操作数的目的,函数命名op(i,e)可以描述如下:
能AC 通过的c++代码,包括zoj1002,1091,1789
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
zoj的代码实现,很好,而且很全面,全部实现。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
ZOJ上的一些水题,4.16浙江省程序设计竞赛的题目
zoj题目简单归类zoj题目简单归类zoj题目简单归类
zoj 2536 这个不是用贪心做的
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法