C++贪心算法二（练习题）

贪心算法二-训练1-1字典序最小的字符串删除k个字符【描述】给定字符串s和整数k删除k个字符后得到字典序最小的字符串。【输入描述】字符串s整数k保证k s.length()【输出描述】删除后的最小字典序字符串。【样例输入】helloword3【样例输出】ellood#includeiostream#includealgorithm#includestringusingnamespacestd;intmain(){string s;// 输入的数字字符串intk;// 需要删除的字符个数cinsk;string result;// 遍历原字符串中的每一个字符for(charcurrent_char:s){// 贪心策略尽可能让前面的数字更小while(!result.empty()k0result.back()current_char){result.pop_back();// 删除末尾较大的字符k--;// 剩余删除次数减1}result.push_back(current_char);// 将当前字符加入结果}// 处理可能剩余的删除次数例如所有字符递增时需要删除末尾的k个字符if(k0){result.resize(result.size()-k);}// 去除前导零例如结果为0200时应输出200size_t first_non_zeroresult.find_first_not_of(0);if(first_non_zerostring::npos){// 所有字符都是0的情况如000cout0;}else{// 存在非零字符输出从第一个非零字符开始的子串coutresult.substr(first_non_zero);}return0;}/* 【输入用例2】 goodmorning 5 【输出用例2】 dmning 【输入用例3】 mynameiszhangsan 9 【输出用例3】 aangsan 【输入用例4】 whatisyuoename 4 【输出用例4】 aisuoename 【输入用例5】 stringandlength 7 【输出用例5】 adlength 【输入用例6】 includeiostreamalgorithmstring 15 【输出用例6】 aagorithmstring */贪心算法二-训练1-2图书排序价格作者【描述】输入n本书的价格和作者按价格升序、价格相同按作者字典序升序排列。【输入描述】一个数n随后n行每行一个整数价格和一个字符串作者。【输出描述】排序后的图书列表。【样例输入】3200 李四100 张三150 王五【样例输出】100 张三150 王五200 李四#includeiostream#includealgorithm#includestringusingnamespacestd;structBook{intprice;// 书的价格string author;// 书的作者};boolcompare(Book a,Book b){// 比较价格if(a.price!b.price){returna.priceb.price;// 按价格升序排列价格低的在前}// 价格相同比较作者名returna.authorb.author;// 按作者名的字典序升序排列字母顺序靠前的在前}intmain(){intn;cinn;// 输入书的数量// 创建一个Book类型的数组最多可以存储100本书Book books[100];// 循环读取每本书的价格和作者信息for(inti0;in;i){cinbooks[i].pricebooks[i].author;}sort(books,booksn,compare);// 循环输出排序后的书籍信息for(inti0;in;i){coutbooks[i].price books[i].authorendl;}return0;}/* 【输入用例2】 2 200 王五 200 李四 【输出用例2】 200 李四 200 王五 【输入用例3】 2 150 张三 150 张三 【输出用例3】 150 张三 150 张三 【输入用例4】 1 300 赵六 【输出用例4】 300 赵六 【输入用例5】 3 300 张三 200 李四 100 王五 【输出用例5】 100 王五 200 李四 300 张三 【输入用例6】 2 120 Bob 120 Alice 【输出用例6】 120 Alice 120 Bob */贪心算法二-训练1-3删减字符使递增【描述】输入一个字符串小写或大写字母按照从左到有的顺序当后一个字符要大于前一个字符时保留否则删除后一个字母字符最后使字符串严格递增。【输入描述】字符串s【输出描述】处理后的字符串严格递增。【样例输入】helloword【样例输出】hlow#includeiostream#includealgorithmusingnamespacestd;intmain(){string s;cins;string res;charlast0;// 初始为最小字符for(charc:s){if(clast){// 只保留比上一个大的字符res.push_back(c);lastc;}}coutresendl;return0;}/* 【输入用例2】 ABCdef 【输出用例2】 ABCdef 【输入用例3】 include 【输出用例3】 inu 【输入用例4】 iostream 【输出用例4】 iost 【输入用例5】 algorithm 【输出用例5】 alort 【输入用例6】 usingnamespace 【输出用例6】 u */贪心算法二-训练2-1分发饼干【描述】假设你是一位很棒的家长想要给你的n个孩子们分发m块小饼干。但是每个孩子最多只能给一块饼干。对每个孩子 i 都有一个胃口值 gi 这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j 都有一个尺寸 sj 。如果 sj gi 我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子并输出这个最大数值。【输入描述】 第一行一个正整数n表示孩子数量n10后面一行 n个正整数表示每个孩子的胃口值g。第三行一个正整数 m表示饼干的数量m20 后面一行 m个正整数表示每块饼干的尺寸s。【输出描述】 最多能满足多少孩子。【输入样例1】31 2 321 1【输出样例1】1【输入样例2】21 232 1 3【输出样例2】2【思路】 典型贪心策略尽可能的用小饼干喂饱胃口小的孩子。首先将两个数组升序排序顺序遍历两个数组1、如果当前饼干喂不饱当前的小孩那么后面所有的小孩肯定也喂不饱所以直接查看下一个饼干能否喂饱当前的小孩直到一个饼干可以喂饱当前的小孩统计结果加12、继续给下一个孩子找饼干。#includeiostream#includealgorithmusingnamespacestd;intg[11];ints[21];intmain(){intn,m;cinn;for(inti0;in;i)cing[i];cinm;for(inti0;im;i)cins[i];// 首先将两个数组从小到大排序sort(g,gn);sort(s,sm);inti0,j0,ans0;// i作为g指针j为s指针while(injm){if(s[j]g[i]){// 满足了一个小孩g指针后移1ans加1i;ans;}// 不管当前饼干是否可以满足此小孩s指针都向后移1j;}coutans;return0;}/* 【输入用例2】 3 1 2 3 3 1 1 2 【输出用例2】 2 【输入用例3】 3 1 2 3 3 3 4 5 【输出用例3】 3 【输入用例4】 3 5 6 7 3 1 2 3 【输出用例4】 0 【输入用例5】 4 2 2 2 2 4 2 2 2 2 【输出用例5】 4 【输入用例6】 4 1 1 2 2 4 1 1 2 2 【输出用例6】 4 */贪心算法二-训练2-2分配任务给工人最大时间最小化【描述】n个任务处理时间已知分配给m个工人n m求最终输出所有工人中总处理时间的最大值即最忙工人的总耗时。【输入描述】n任务数m工人数随后n个整数任务时间【输出描述】最忙工人的总耗时【样例输入】3 35 3 1【样例输出】5#includeiostream#includealgorithmusingnamespacestd;intmain(){intn,m;cinnm;//输入任务数量n和工人数量m。inttasks[100];for(inti0;in;i){cintasks[i];}sort(tasks,tasksn,greaterint());// 降序排列intworkers[100]{0};for(inti0;in;i){workers[i%m]tasks[i];// 轮流分配给工人}intmaxTime0;for(inti0;im;i)//遍历所有工人找到总耗时最大的值。{if(workers[i]maxTime)maxTimeworkers[i];}coutmaxTimeendl;return0;}/* 【输入用例2】 2 3 4 2 【输出用例2】 4 【输入用例3】 5 2 10 8 6 4 2 【输出用例3】 18 【输入用例4】 4 2 5 5 5 5 【输出用例4】 10 【输入用例5】 3 1 3 1 2 【输出用例5】 6 【输入用例6】 4 2 7 6 5 4 【输出用例6】 12 */贪心算法二-训练2-3股票买卖最佳时机【描述】给定每天股价求一次交易买入后卖出能获得的最大利润。【输入描述】n天数随后n个整数股价。【输出描述】最大利润无法盈利则输出0。【样例输入】67 1 5 3 6 4【样例输出】5#includeiostream#includealgorithmusingnamespacestd;intmain(){intn;cinn;// 输入股票价格的天数intprices[100];// 存储每天的股票价格for(inti0;in;i){cinprices[i];// 输入每天的价格}// minPrice记录遍历到当前时遇到的最低价格初始为第一天的价格// maxProfit记录当前能获得的最大利润初始为0即不交易的情况intminPriceprices[0],maxProfit0;// 从第二天开始遍历因为第一天只能买入无法卖出for(inti1;in;i){if(prices[i]minPrice){// 如果今天的价格比之前记录的最低价格还低更新最低价格为今天的价格minPriceprices[i];}else{// 如果今天的价格不低于最低价格计算今天卖出的利润今天价格 - 最低买入价并更新最大利润取当前最大利润和新利润中的较大值maxProfitmax(maxProfit,prices[i]-minPrice);}}coutmaxProfitendl;// 输出最大利润return0;}/* 【输入用例2】 4 1 2 3 4 【输出用例2】 3 【输入用例3】 3 5 4 3 【输出用例3】 0 【输入用例4】 5 3 8 1 2 9 【输出用例4】 8 【输入用例5】 5 2 2 1 1 3 【输出用例5】 2 【输入用例6】 5 5 4 3 2 10 【输出用例6】 8 */