企业建设项目哪个网站可以查,深圳光明建设局官方网站,企业域名备案流程详细,郑州哪有做网站的汉狮题目描述又是一年秋季时#xff0c;陶陶家的苹果树结了n个果子。陶陶又跑去摘苹果#xff0c;这次她有一个a公分的椅子。当他手够不着时#xff0c;他会站到椅子上再试试。这次与NOIp2005普及组第一题不同的是#xff1a;陶陶之前搬凳子#xff0c;力气只剩下s了。当然陶陶家的苹果树结了n个果子。陶陶又跑去摘苹果这次她有一个a公分的椅子。当他手够不着时他会站到椅子上再试试。这次与NOIp2005普及组第一题不同的是陶陶之前搬凳子力气只剩下s了。当然每次摘苹果时都要用一定的力气。陶陶想知道在s0之前最多能摘到多少个苹果。现在已知n个苹果到达地上的高度xi椅子的高度a陶陶手伸直的最大长度b陶陶所剩的力气s陶陶摘一个苹果需要的力气yi求陶陶最多能摘到多少个苹果。输入输出格式输入格式第1行两个数 苹果数n力气s。第2行两个数 椅子的高度a陶陶手伸直的最大长度b。第3行~第3n-1行每行两个数 苹果高度xi摘这个苹果需要的力气yi。输出格式只有一个整数表示陶陶最多能摘到的苹果数。输入输出样例输入样例#1输出样例#18 1520 130120 3150 2110 7180 150 8200 0140 3120 24说明所有数据n5000 a50 b200 s1000xi280 yi100思路咳首先由于前几天刚刚学了什么是“深度优先搜索(DFS)”看到这道题我第一反应是这个不就是用深度优先搜索吗把所有情况全部列举出来然后再在满足条件的情况下选择能摘到最多苹果的情况不就AC了吗自我感觉非常良好还自以为很聪明。我还在输入的时候就把摘不到的苹果忽略了以此来减少列举情况节约时间。于是写了这样的代码代码#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;}elsescanf(%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;}最后的结果当然AC了 ,好吧…TLE了…感觉瞬间自己被自己打脸。然后再次经过不断思考发现只要将可以摘到的苹果用“快速排序”将要用的力气从小到大排序出来然后从最小的力气一直累加直到累加值淘淘拥有的力气这时候就可以得到摘到最多苹果的值了。ps.这时候要注意苹果为0的情况。和累加是大于力气还是等于力气这两种不同情况的时候要对值做不同的处理。所以最终获得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;}elsescanf(%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);}最后的体会是做题不能想当然要思考用最快的方法而不是用自己感觉很厉害的方法。
