删数问题贪心算法

❶ C++删数问题

关键在于理解算法的思想，从你的代码来看你的思路并不是很清楚
既然贪心，首先就想到贪心的本质，再联系题目的要求
贪心是意思是每次的结果都在当前是最优解
作为本题来看，就是每次删除一个数之后都是比删除其它数更小的
那么什么情况会发生呢，这就是思考的要点了，这里就可以模拟几组数来进行删除实验
发现一定会是前面的数比后面的数大的时候删除它就能得到一个最优解
那么接下来代码就会很好写了

其实最重要的不是代码，而是如何从题目变成一个正确的算法，也即思考的过程
希望能解决您的问题。

❷ c语言删数问题

这个题目其实你想复杂了，3L说的完全是对的。也许你看的不是很懂。
那么这么给你讲吧，就是从数据的最高位往后面扫描。如果发现相邻的2个数据中，右边的比左边的小，那么就将左边的那个数减掉，不然就剪掉最大的那个数值。
然后，继续重复开始扫描，直到删除的个数满足就达到目的了。
比如：123546
删除5之后，这个数绝对是最小的了，至于原因，你可以试试删除其他数然后比较比较就知道了。
一直继续下去，保证每一次删除数据之后都是最小值，结构就自然出来了。

❸ 5.贪心算法的核心思想。6.什么是递归什么是迭代两者的区别，举例说明。7.回溯的含义是什么举例

1、贪心算法主要是把问题分成很多局部问题，用局部最优解合成整体最优解。因此使用这种算法需要此问题满足两个条件，一个是能够分成多个能够求解的局部问题，第二个就是局部问题的解能够合成最优解。和动态规划、回溯等相比差别就是再不回溯的前提下找出整体最优解或者接近最优解，速度快但应用有比较大的限制。

2、迭代也叫递推，通过重复执行某一步骤或者函数来求得计算结果
递归是指函数中直接或者间接调用自身
举例：
求a乘以2的10次方等于几
迭代：
for (i=0;i<10;i++)
a *= 2;

递归：
int db(int a,int num)
{
if (num<10)
return 2 * db(a,num+1);
else
return 1;
}

db(a,0);

3、回溯的含义就是在搜索问题的状态过程中，如果不能继续前进，再向后回到岔口，换一条路继续搜索，直到搜索完所有状态或者查找到需要的状态。
举例：（最典型的就是树的深度搜索，下面举一个简单的例子）
int a[10]={5,3,7,9,3,2,5,6,9,1};//从3开始查找1
int read[10]=(0);//是否查找过
int readNum = 0;//查找过的个数
int forward = 1;//1为左，2为右
int tmp = 0,index = 5;

tmp = a[index];
read[index] = 1;
readNum++;
while (tmp != 1 || readNum != 10)
{
if (forward == 1)
index --;
else
index++;
if (!read[index])
{
tmp = a[index];
read[index] = 1;
readNum++;
}

if (index <=0 || index>=9)
forward = 3 - forward;
}

❹ 在ISO-C++中如何实现随机贪心法

7.1 贪心策略的定义
7.2 贪心策略特点
7.3 典型例题与习题

在众多的计算机解题策略中，贪心策略可以算得上是最接近人们日常思维的一种解题策略，正基于此，贪心策略在各级各类信息学竞赛、尤其在对NPC类问题的求解中发挥着越来越重要的作用。

7.1 贪心策略的定义

贪心策略是：指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。

其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。
例1：在n行m列的正整数矩阵中，要求从每一行中选一个数，使得选出的n个数的和最大。

本题可用贪心策略：选n次，每一次选相应行中的最大值即可。

例2：在一个N×M的方格阵中，每一格子赋予一个数（即为权）。规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。

本题用贪心策略不能得到最优解，我们以2×4的矩阵为例。 3 4 6
1 2 10

若按贪心策略求解，所得路径为：1,3,4,6；

若按动态规划法求解，所得路径为：1,2,10,6。

例3:设定有n台处理机p1，p2，......pn,和m个作业j1,j2,...jm,处理机可并行工作,作业未完成不能中断，作业ji在处理机上的处理时间为ti,求解最佳方案,使得完成m项工作的时间最短?

本题不能用贪心算法求解:理由是若n=3,m=6 各作业的时间分别是11 7 5 5 4 7

用贪心策略解(每次将作业加到最先空闲的机器上)time=15,用搜索策略最优时间应是14,但是贪心策略给我们提供了一个线索那就是每台处理上的时间不超过15,给搜索提供了方便。

总之：
1. 不能保证求得的最后解是最佳的；
2. 只能用来求某些最大或最小解问题；
3. 能确定某些问题的可行解的范围，特别是给搜索算法提供了依据。

7. 2 贪心策略的特点
贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2个特点：

1、贪心选择性质：

所谓贪心选择性质是指应用同一规则f，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后文给出的贪心策略状态空间图中得到深刻地体会。

2、局部最优解：

我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了最优解，但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，但贪心策略比动态规划时间效率更高站用内存更少，编写程序更简单。

7.3 典型例题与习题

例4：背包问题：

有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品
A
B
C
D
E
F
G

重量
35
30
60
50
40
10
25

价值
10
40
30
50
35
40
30

分析：

目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)

（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占空间最小的物品装入是否能得到最优解？
（3）每次选取单位容量价值最大的物品，成为解本题的策略。

程序如下：

program beibao;

const
m=150;
n=7;
var
xu:integer;
i,j:integer;
goods:array[1..n,0..2] of integer;
ok:array[1..n,1..2] of real;

procere init;
var
i:integer;
begin
xu:=m;
for i:=1 to n do
begin
write('Enter the price and weight of the ',i,'th goods:');
goods[i,0]:=i;
read(goods[i,1],goods[i,2]);
readln;
ok[i,1]:=0; ok[i,2]:=0;
end;
end;

procere make;
var
bi:array[1..n] of real;
i,j:integer;
temp1,temp2,temp0:integer;
begin
for i:=1 to n do
bi[i]:=goods[i,1]/goods[i,2];
for i:=1 to n-1 do
for j:=i+1 to n do
begin
if bi[i]<bi[j] then begin
temp0:=goods[i,0]; temp1:=goods[i,1]; temp2:=goods[i,2];
goods[i,0]:=goods[j,0]; goods[i,1]:=goods[j,1]; goods[i,2]:=goods[j,2];
goods[j,0]:=temp0; goods[j,1]:=temp1; goods[j,2]:=temp2;
end;
end;
end;

begin
init;
make;
for i:=1 to 7 do
begin
if goods[i,2]>xu then break;
ok[i,1]:=goods[i,0]; ok[i,2]:=1;
xu:=xu-goods[i,2];
end;
j:=i;
if i<=n then
begin
ok[i,1]:=goods[i,0];
ok[i,2]:=xu/goods[i,2];
end;
for i:=1 to j do
writeln(ok[i,1]:1:0,':',ok[i,2]*goods[i,2]:2:1);
end.

例5：旅行家的预算问题：

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市，给定两个城市间的距离d1，汽车油箱的容量是c，每升汽油能行驶的距离d2，出发时每升汽油的价格是p，沿途加油站数为n（可为0），油站i离出发点的距离是di，每升汽油的价格是pi。

计算结果四舍五入保留小数点后两位，若无法到达目的地输出“No answer"

若输入：

d1=275.6 c=11.9 d2=27.4 p=8 n=2

d[1]=102 p[1]=2.9

d[2]=220 p[2]=2.2

output

26.95

本问题的贪心策略是：找下一个较便宜的油站，根据距离确定加满、不加、加到刚好到该站。

程序如下:

program jiayou;
const maxn=10001;
zero=1e-16;
type
jd=record
value,way,over:real;
end;
var oil:array[1..maxn] of ^jd;
n:integer;
d1,c,d2,cost,maxway:real;
function init:boolean;
var i:integer;
begin
new(oil[1]);
oil[1]^.way:=0;
read(d1,c,d2,oil[1]^.value,n);
maxway:=d2*c;
for i:=2 to n+1 do
begin
new(oil[i]);
readln(oil[i]^.way,oil[i]^.value);
oil[i]^.over:=0;
end;
inc(n,2);
new(oil[n]);
oil[n]^.way:=d1;
oil[n]^.value:=0;
oil[n]^.over:=0;
for i:=2 to n do
if oil[i]^.way-oil[i-1]^.way>maxway then
begin
init:=false;
exit
end;
init:=true;
end;
procere buy(i:integer;miles:real);
begin
cost:=cost+miles/d2*oil[i]^.value;
end;
procere solve;
var i,j:integer;
s:real;
begin
i:=1;j:=i+1;
repeat
s:=0.0;
while( s<=maxway+zero) and (j<=n-1) and (oil[i]^.value<=oil[j]^.value) do
begin
inc(j);
s:=s+oil[j]^.way-oil[j-1]^.way
end;
if s<=maxway+zero then
if (oil[i]^.over+zero>=oil[j]^.way-oil[i]^.way) then
oil[j]^.over:=oil[i]^.over-(oil[j]^.way-oil[i]^.way) else
begin
buy(i,oil[j]^.way-oil[i]^.way-oil[i]^.over);
oil[j]^.over:=0.0;
end
else begin
buy(i,maxway-oil[i]^.over);
j:=i+1;
oil[j]^.over:=maxway-(oil[j]^.way-oil[i]^.way);
end;
i:=j;
until i=n;
end;
begin
cost:=0;
if init then begin
solve;
writeln(cost:0:2);
end else writeln('No answer');
end.

例6:n个部件,每个部件必须经过先A后B两道工序。

以知部件i在A,B 机器上的时间分别为ai，bi。如何安排加工顺序，总加工时间最短？

输入：

5 部件 1 2 3 4 5
ai 3 5 8 7 10
bi 6 2 1 4 9

输出：

34

1 5 4 2 3

本问题的贪心策略是A机器上加工短的应优先，B机器上加工短的应靠后。

程序如下：

program workorder;
const maxn=100;
type jd=record
a,b,m,o:integer;
end;
var n,min,i:integer;
c:array[1..maxn] of jd;
order:array[1..maxn] of integer;
procere init;
var i:integer;
begin
readln(n);
for i:=1 to n do
read(c[i].a);
readln;
for i:=1 to n do
read(c[i].b);
readln;
for i:=1 to n do
begin
if c[i].a<c[i].b then c[i].m:=c[i].a else c[i].m:=c[i].b;
c[i].o:=i;
end;
end;
procere sort;
var i,j,k,t:integer;
temp:jd;
begin
for i:=1 to n-1 do
begin
k:=i;t:=c[i].m;
for j:=i+1 to n do
if c[j].m<t then begin t:=c[j].m;k:=j end ;
if k<>i then begin temp:=c[i];c[i]:=c[k];c[k]:=temp end
end;
end;
procere playorder;
var i,s,t:integer;
begin
fillchar(order,sizeof(order),0);
s:=1;
t:=n;
for i:=1 to n do
if c[i].m=c[i].a then begin order[s]:=i;s:=s+1 end
else begin order[t]:=i;t:=t-1;end;
end;
procere calc_t;
var i,t1,t2:integer;
begin
t1:=0;t2:=0;
for i:=1 to n do
begin
t1:=t1+c[order[i]].a;
if t2<t1 then t2:=t1;
t2:=t2+c[order[i]].b;
end;
min:=t2;
end;
begin
init;
sort;
playorder;
calc_t;
writeln(min);
for i:=1 to n do
write(c[order[i]].o,' ');
writeln;
end.

习题：

1.最佳浏览路线问题:

某旅游区的街道成网格状（见图），其中东西向的街道都是旅游街，南北向的街道都是林荫道。由于游客众多，旅游街被规定为单行道。游客在旅游街上只能从西向东走，在林荫道上既可以由南向北走，也可以从北向南走。阿隆想到这个旅游区游玩。他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之间的道路值得浏览得程度，分值从-100到100的整数，所有林荫道不打分。所有分值不可能全是负值。

例如下图是被打过分的某旅游区的街道图：

图6

阿隆可以从任一路口开始浏览，在任一路口结束浏览。请你写一个程序，帮助阿隆寻找一条最佳的浏览路线，使得这条路线的所有分值总和最大。

2..删数问题

键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按左右次序组成一个新的正整数。对给定的N和S，寻找一种删数规则使得剩

❺ NOIP2003。删数游戏，

【问题分析】
对于这道试题，一般可以采用这样一种解题方式：因为要删除S个数字，可以一个一个的删，每一次删除的目的都是使剩下的数尽量小。那么在每一次删除时，应该选择那个数字？最大的数字还是最左的数字？例如5768，通过观察可以知道删除7这个数字可以使剩余的数最小。通过思考可以得出结论，每一次删除的数字应该是这个数字序列中降序子序列最左边的数字。具体可以这样操作，按高位到低位的方向搜索递减区间。若不存在递减区间，则删尾数符；否则删递减区间的首数符，这样形成了一个新的数串。然后回到串首，重复上述规则，删下一数符…以此类推，直至删除S个数符为止。
例如：N=“8796542”，S=4删数过程如下：
N=“8 7 9 6 5 4 2” //最左边的递减序列是87，删除“8”
“7 9 6 5 4 2” //最左边的递减序列是96542，删除9
“7 6 5 4 2” //最左边的递减序列是76542，删除“7”
“6 5 4 2” //最左边的递减序列是6542，删除“6”
“5 4 2”
【程序代码】
program delete;
var i，j，k，s:integer;
N:string;
begin
readln(n);
readln(s);
while s>0 do begin
I:=1;
while (i<length(n)) and (n[i]<=n[i+1]) do
Inc(i);
delete(n，I，1);
dec(s);
end;
while (length(n)>1 and (n[1]=‘0’) do
delete(n，1，1)；
writeln(n);
end.
【问题思考】
由题可知，贪心算法的实现需要思考两个基本的问题：如何建立和方法的正确性。
如何建立。怎样从一个规模较小的解推出规模较大的解呢？拿这个例题来说，从数串5768删除2位数的模拟过程中推广到240位的数串删数过程。
方法的正确性。确保贪心算法确实是有效是使用贪心算法的关键所在。确定贪心算法是有效的，那么解决该问题在时间复杂度还是在空间的使用方面与其他方法想比较显得更为优势。以例题为例，删数方法是首先按高位到低位的方向搜索递减区间。若不存在递减区间，则删尾数符；否则删递减区间的首数符，这样形成了一个新的数串。这样获得的新数肯定是最小的新数。
对于上述例题，假如我们按照其他的删数过程是正确的，删除最左边的数或者每次删除最大的数。同样以5768为例。删除5得768，删除8得576，都不是最小的数值，假设不成立，证明这种方式是错误的，按照原先设定的方法所得到的解是最优解。
由上例可以获知，贪心的使用需要严格的证明，保证问题的严密性，贪心方法的使用还需结合其他算法的使用，例如：排序、模拟、搜素、枚举等等，但是一旦证明了贪心方法使用的正确性，程序的运行效率会大大提高。证明使用贪心方法的正确性依靠的是严密的数学头脑和以往的经验积累，假如不具备这些条件，使用该方法需要谨慎。

❻ 贪心算法问题

//身为大一菜鸟的我曾错了n次的题
//算法是从头开始扫过去，若当前扫到的数比下一个大，则删，删后回退到上一个未被删的数继续，直到删完指定数或扫到最后一个元素，若删不够指定的数，则此刻数组肯定是递增的，所以只要从后向前删至足够数量便行了

#include<iostream>
#include<string.h>
using namespace std;
char str[250];
int a[250];
int b[250];

int main(){
int i, len, k, l, r, c, t, f;
do{
f = 0;
cin >> str;
if (str[0] == '0')
break;
len = strlen(str);
cin >> k;
for (i = 0; i<250; i++){
a[i] = i + 1;
b[i] = i - 1;
}
c = 0;
l = 0;
for (r = 1; str[r] != '\0';){
if (c >= k)
break;
if (str[r] - str[l] >= 0){
l = a[l];
r = a[r];
}
else{
c++;
if (b[l] != -1){
a[b[l]] = r;
b[r] = b[l];
l = b[l];
}
else{
f = 1;
b[r] = -1;
a[0] = r;
l = a[l];
r = a[r];
}
}
}
t = r - 1;
for (; c<k; c++){
a[b[t]] = r;
t = b[t];
}
if (f == 0)
cout << str[0];
i = 0;
for (i = a[i]; i<len; i = a[i]){
cout << str[i];
}
cout << endl;
} while (1);
return 0;
}

❼ Python贪心算法

所谓贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优加以考虑，它所做出的仅仅是在某种意义上的局部最优解。下面让我们来看一个经典的例题。假设超市的收银柜中有1分、2分、5分、1角、2角、5角、1元的硬币。
顾客结账如果需要找零钱时，收银员希望将最少的硬币数找出给顾客，那么，给定需要找的零钱数目，如何求得最少的硬币数呢？这个找零钱的基本思路：每次都选择面值不超过需要找给顾客的钱最大面值的硬币。
我们可以从面值最大的硬币开始，然后依次递减（图1）。
首先定义列表d存储已有币值。并且定义d_num存储每种币值的数量。通过循环遍历的方法计算出收银员拥有钱的总金额并保存在变量S中，要找的零钱变量为sum。当找零的金_比收银员的总金额多时，无法进行找零，提示报错。要想用的钱币数量最少，我们从面值最大的币值开始遍历。这里也就是我们贪心算法的核心步骤。计算出每种硬币所需要的数量，不断地更新硬币个数与硬币面值，最终获得一个符合要求的组合（图2）。
贪心算法在对问题求解时，不是对所有问题都能得到整体最优解，也不是从整体上去考虑，做出的只是在某种意义上的局部最优解。从面值最大的硬币开始依次递减，寻找可用的方法。一般贪心算法并不能保证是最佳的解决方法，这是因为：总是从局部出发没有从整体考虑，只能确定某些问题是有解的，优点是算法简单。常用来解决求最大值或最小值的问题。来源：电脑报

❽ C语言 删数问题

#include<stdio.h>
#include<string.h>
int main()
{
void shchu(char *a,int k);
int k;
while(1)
{
char a[500];
scanf("%s",a);
if(a[0]=='0')break;//输入数据结束时的标志
scanf("%d",&k);
shchu(a,k);
printf("%s\n",a);
}
return 0;
}
void shchu(char *a,int k)
{
int i,j,sign=0;//sign用来表示整个字符串中
//是不是有前面一个字符比后面的一个字符大的
if(k==0)
return;//递归结束的标志
for(i=0;i<strlen(a);++i)
if(a[i]>a[i+1])
{sign=1;break;}
if(sign)
{
for(j=i;j<strlen(a)-1;++j,++i)
a[j]=a[i+1];
a[j]='\0';
}//实现的是把较大的那一个字符删去
else
a[strlen(a)-1]='\0';//这是排好时的情况，使它的
shchu(a,k-1);//最后一个元素变成'\0'即可
}

❾ 求一个算法(贪心算法)

贪心算法

一、算法思想

贪心法的基本思路：
——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：
1. 不能保证求得的最后解是最佳的；
2. 不能用来求最大或最小解问题；
3. 只能求满足某些约束条件的可行解的范围。

实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；

二、例题分析

1、[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30

分析：

目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)

（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占重量最小的物品装入是否能得到最优解？
（3）每次选取单位重量价值最大的物品，成为解本题的策略。 ?

值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
（1）贪心策略：选取价值最大者。反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
（3）贪心策略：选取单位重量价值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。

所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）

================================
三个经典的贪心算法

有人说贪心算法是最简单的算法，原因很简单：你我其实都很贪，根本不用学。有人说贪心算法是最复杂的算法，原因也很简单：这世上贪的人太多了，那轮到你我的份？

不论难度如何，贪心算法都是一个很重要的算法，我在网上N多Online Judge中的题目中，总结了三类较为常见，也十分经典的贪心算法，发布在这儿Just For Fun。

（注：由于没有现成的名字可用，这三种类型贪心算法的名字都是我自己取的，如果你听着别扭，请见谅。）

No 1.线段覆盖（linescover）

题目大意：

在一维空间中告诉你N条线段的起始坐标与终止坐标，要求求出这些线段一共覆盖了多大的长度。

解题思路：

将线段按其坐标进行排序（排序的具体方法:按起始坐标排，起始坐标相同的按终止坐标排，都是小在前大在后）,使之依次递增，并按顺序分别编号为X(i),X(i).a代表其起始坐标，X(i).b代表其终止坐标。

然后按排好的顺序依次处理：定义一个变量last记录考虑到当前线段之时被线段覆盖的最大的坐标值，再定义一个变量length记录当前线段覆盖的长度。对于后面的线段，我们把它看成由两个部分组成，即把它分成last之前的线段和last之后的线段。（如果线段全部处在last之后，其last之前的部分不存在。）由于我们排过序，我们可以肯定当前考虑的线段X(i)其处在last之前的部分不会对length造成影响（因为X(i-1).b=last，X(i).a>=X(i-1).a,即X(i)在last之前的部分所处位置肯定被线段X(i-1)覆盖过），所以会对length产生影响的即是X(i)处在last之后的部分。

所以我们可以依次对每条线段做如下处理：（初始化length为零，last为负无穷）

length+=X(i).b-last (X(i).a<=last 且 X(i).b>=last)

length+=X(i).b-X(i).a (X(i).a>last)

last=X(i).b;

最后length就为我们所需要的答案。

No 2.最优数对（bestpair）

题目大意：

按递增的顺序告诉你N个正整数和一个实数P，要求求出求出该数列中的比例最接近P的两个数（保证绝对没有两个数使得其比值为P）。

解题思路：

定义两个指针i和j，先初始化i=j=1，然后进行如下操作：

当code[j]/code[i]>p时，inc（j）；

当code[j]/code[i]<p时，inc（i）。

记录其中产生的最优值即为答案。

No 3.连续数之和最大值（maxsum）

题目大意：

给出一个长度为N的数列（数列中至少有一个正数），要求求出其中的连续数之和的最大值。（也可以加入a和b来限制连续数的长度不小于a且不大于b）。

解题思路：

先说不加限制的那种，定义一个统计变量tot，然后用循环进行如下操作：inc（tot，item） 其中如果出现tot<0的情况，则将tot赋值为0。在循环过程之中tot出现的最大值即为答案。

如果加入了限制条件的话，问题就变得难一些了（这句真的不是废话）。为此我们先定义数组sum[i]来表示code[1]到code[i]之和（这样的话code[a]~code[b]的和我们就可以用sum[b]-sum[a-1]来表示了。）。

再维护一个数组hash[i]来表示满足条件的sum[a-1]的下标，并使之按递增顺序排列，这样当前以第i的数为终止的数列的最大值肯定就是sum[i]-sum[hash[1]]。

现在我们来讨论hash数组之中的数据需要满足的条件和如何维护的具体问题：

当考虑到以第i个数为结尾时，hash[i]所表示的下标需要满足的第一个条件就是题目规定的长度限制，我们需要实时的加入满足长度规定的下标，删除不符合要求的下标。其次，与不加限制条件时相同，若sum[i]-sum[hash[1]]的值小于零，则清空数组hash。

维护时可以这样，当考虑到第i个数时，我们就将下标i-a+1加入到hash中，因为hash中原来已经排好序，因此我们我们可以用插入排序来维护hash的递增性，然后我们考察hash[1]，若hash[1]<i-b+1，则证明其已超出长度限制，我们就将其删除，接着再考虑更新后的hash[1],如此重复直至找到一个满足条件的hash[1]为止。

我们可以用链表来表示hash，这样就可以减少数据加入和删除时频繁数据移动的时间消耗。

记录下sum[i]-sum[hash[1]]的最大值即为答案。