原題地址：P1478 淘淘摘蘋果(升級(jí)版)- 洛谷

題目描述

又是一年秋季時(shí)，陶陶家的蘋果樹結(jié)了n個(gè)果子。陶陶又跑去摘蘋果，這次她有一個(gè)a公分的椅子。當(dāng)他手夠不著時(shí)，他會(huì)站到椅子上再試試。

這次與NOIp2005普及組第一題不同的是：陶陶之前搬凳子，力氣只剩下s了。當(dāng)然，每次摘蘋果時(shí)都要用一定的力氣。陶陶想知道在s<0之前最多能摘到多少個(gè)蘋果。

現(xiàn)在已知n個(gè)蘋果到達(dá)地上的高度xi，椅子的高度a，陶陶手伸直的最大長度b，陶陶所剩的力氣s，陶陶摘一個(gè)蘋果需要的力氣yi，求陶陶最多能摘到多少個(gè)蘋果。

輸入輸出格式

輸入格式：

第1行：兩個(gè)數(shù) 蘋果數(shù)n，力氣s。

第2行：兩個(gè)數(shù) 椅子的高度a，陶陶手伸直的最大長度b。

第3行~第3+n-1行：每行兩個(gè)數(shù) 蘋果高度xi，摘這個(gè)蘋果需要的力氣yi。

輸出格式：

只有一個(gè)整數(shù)，表示陶陶最多能摘到的蘋果數(shù)。

輸入輸出樣例

輸入樣例#1：

輸出樣例#1：

8 15

20 130

120 3

150 2

110 7

180 1

50 8

200 0

140 3

120 2

4

說明

所有數(shù)據(jù)：n<=5000 a<=50 b<=200 s<=1000

xi<=280 yi<=100

思路

咳，首先由于前幾天剛剛學(xué)了什么是“深度優(yōu)先搜索(DFS)”，看到這道題，我第一反應(yīng)是：這個(gè)不就是用深度優(yōu)先搜索嗎？！把所有情況全部列舉出來，然后再在滿足條件的情況下選擇能摘到最多蘋果的情況，不就AC了嗎？！

自我感覺非常良好，還自以為很聰明。我還在輸入的時(shí)候就把摘不到的蘋果忽略了，以此來減少列舉情況，節(jié)約時(shí)間。

于是寫了這樣的代碼：

代碼

#include

void dfs(int s, int num);

int apple[5005], book[5005];

int max = 0, n, t = 0;

int main()

{

int s, a, b, i, max1, xi;

scanf("%d%d%d%d", &n, &s, &a, &b);

max1 = a + b;

for(i = 0; i < n; i++)

{

scanf("%d", &xi);

if(xi <= max1)

{

scanf("%d", &apple[t]);

t++;

}

else

scanf("%d", &xi);

}

dfs(s, 0);

printf("%d", max);

return 0;

}

void dfs(int s, int num)

{

int i;

if(s <= 0 || num == t)

{

if(s < 0)

num--;

if(num > max)

max = num;

return;

}

for(i = 0; i < t; i++)

{

if(book[i] == 0)

{

book[i] = 1;

dfs(s - apple[i], num + 1);

book[i] = 0;

}

}

return;

}

最后的結(jié)果當(dāng)然AC了 ,好吧…TLE了…感覺瞬間自己被自己打臉。

然后再次經(jīng)過不斷思考發(fā)現(xiàn)，只要將可以摘到的蘋果用“快速排序”將要用的力氣從小到大排序出來，然后從最小的力氣一直累加，直到累加值>=淘淘擁有的力氣，這時(shí)候就可以得到摘到最多蘋果的值了。

ps.這時(shí)候要注意，蘋果為0的情況。和累加是大于力氣，還是等于力氣，這兩種不同情況的時(shí)候要對值做不同的處理。

所以最終獲得AC了！我果然是天才！

AC代碼

#include

void quicksort(int left, int right);

int apple[5005];

int main()

{

int s, n, a, b, i, t = 0, max1, xi, sum = 0;

scanf("%d%d%d%d", &n, &s, &a, &b);

max1 = a + b;

for(i = 0; i < n; i++)

{

scanf("%d", &xi);

if(xi <= max1)

{

scanf("%d", &apple[t]);

t++;

}

else

scanf("%d", &xi);

}

if(n == 0)

{

printf("0");

return 0;

}

quicksort(0, t - 1);

for(i = 0; i < t; i++)

{

sum += apple[i];

if(sum == s)

{

printf("%d", i + 1);

return 0;

}

else if(sum > s)

{

printf("%d", i);

return 0;

}

}

return 0;

}

void quicksort(int left, int right)

{

int i, j, temp, t;

if(left > right)

return;

temp = apple[left], i = left, j = right;

while(i != j)

{

while(apple[j] >= temp && i < j)

j--;

while(apple[i] <= temp && i < j)

i++;

if(i < j)

{

t = apple[i];

apple[i] = apple[j];

apple[j] = t;

}

}

apple[left] = apple[i];

apple[i] = temp;

quicksort(left, i - 1);

quicksort(i + 1, right);

}

最后的體會(huì)是：做題不能想當(dāng)然，要思考用最快的方法，而不是用自己感覺很厲害的方法。

總結(jié)

以上是生活随笔為你收集整理的洛谷找最小值c语言,洛谷 P1478 陶陶摘苹果（升级版） C语言实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。