刪數問題貪心演算法

❶ 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]]的最大值即為答案。