贪心算法3（c++）

概念题目最短前缀题目描述一个字符串的前缀是从该字符串的第一个字符起始的一个子串。例如carbon的字串是:cca,carcarb,carbo,和carbon。我们现在希望能用前缀来缩略的表示单词。例如,carbohydrate通常用carb来缩略表示现在给你一组单词要求你找到唯一标识每个单词的最短前缀在下面的例子中carbohydrate能被缩略成carboh但是不能被缩略成carbo(或其余更短的前缀)因为已经有一个单词用carbo开始输入格式第一行是一个正整数表示输入的单词总数。接下来每行包括一个以小写字母组成的单词单词长度至少是1至多是20.输出格式输出的行数与输入的行数相同。每行输出由相应行输入的单词开始后面跟着一个空格接下来是相应单词的没有二义性的最短前缀标识符样例输入12carbohydratecartcarburetorcaramelcariboucarboniccartilagecarboncarriagecartoncarcarbonate样例输出carbohydrate carbohcart cartcarburetor carbucaramel caracaribou caricarbonic carbonicartilage carticarbon carboncarriage carrcarton cartocar carcarbonate carbona#include bits/stdc.h using namespace std; int n; string a[1010]; int main() { cinn; for(int i 0;in;i) { cina[i]; } for(int i 0;in;i) { for(int j 0;ja[i].size();j) { string b a[i].substr(0,j); bool f true; for(int k 0;kn;k) { if(k!ia[k].substr(0,j)b) { f false; break; } } if(ftrue||ja[i].size()) { couta[i] bendl; break; } } } return 0; }最小新整数题目描述给定一个十进制正整数n(0n1000000000)每个数位上数字均不为0。n的位数为m。现在从m位中删除k位(0k〈m)求生成的新整数最小为多少?例如:n9128456,k2,则生成的新整数最小为12456输入格式第一行t,表示有t组数据;接下来t行每一行表示一组测试数据每组测试数据包含两个数字nk。输出格式t行每行一个数字表示从n中删除k位后得到的最小整数。样例输入29128456 21444 3样例输出124561#include bits/stdc.h using namespace std; string a; int k; int main() { int t; cint; while(t--) { cinak; int n a.size(); while(k!0) { for(int i 0;ia.size();i) { if(i0a[i]a[i1]) { a a.substr(1,a.size()-1); k--; } else if(i!0a[i]a[i-1]a[i]a[i1]) { a a.substr(0,i)a.substr(i1,a.size()-1); k--; } // couti a k nendl; // system(pause); if(k0) break; } if(k0) break; } coutaendl; } return 0; }寻找平面上的极大点题目描述在一个平面上有两个点(x,y),(a,b),如果说(x,y)支配了(a,b)这是指xa且yb;用图形来看就是(a,b)坐落在以(x,y)为右上角的一个无限的区域内。给定n个点的集合一定存在若干个点它们不会被集合中的任何一点所支配这些点叫做极大值点。编程找出所有的极大点按照x坐标由小到大输出极大点的坐标。本题规定:n不超过100并且不考虑点的坐标为负数的情况。输入格式输入包括两行第一行是正整数n表示是点数第二行包含n个点的坐标坐标值都是整数坐标范围从0到100输入数据中不存在坐标相同的点。输出格式按x轴坐标最小到大的顺序输出所有极大点。输出格式为:(x1,y1),(x2,y2)....(xk,yk)样例输入51 2 2 2 3 1 2 3 1 4样例输出(1,4),(2,3),(3,1)#include bits/stdc.h using namespace std; struct node { int x,y; node(){}; node(int aaaaa,int bbbbb) { x aaaaa; y bbbbb; } }; node a[10010]; int n; int main() { cinn; for(int i 1;in;i) { cina[i].xa[i].y; } for(int i 1;in-1;i) { for(int j 1;jn-i;j) { if(a[j].ya[j1].y) { swap(a[j].x,a[j1].x); swap(a[j].y,a[j1].y); } else if(a[j].ya[j1].y) { if(a[j].xa[j1].x) { swap(a[j].x,a[j1].x); swap(a[j].y,a[j1].y); } } } } int cnt 0; int ma -999999999; for(int i 1;in;i) { // couta[i].x a[i].yendl; if(a[i].xma) { ma a[i].x; if(cnt!0) cout,; cnt; printf((%d,%d),a[i].x,a[i].y); } } return 0; }电池寿命题目描述小S新买了一个掌上游戏机由两节5号电池供电。这些电池寿命也有所不同有的能使用5个小时有的可能就只能使用3个小时。如果他只有两个电池5小时和3小时那么他只能玩3个小时的游戏但是如果他有更多的电池就可以更加充分地利用它们比如他有三个电池分别能用3、3、5小时可以先使用两节能用3个小时的电池使用半个小时后再把其中一个换成能使用5个小时的电池两个半小时后再把剩下的一节电池换成刚才换下的电池(那个电池还能用2.5个小时)这样总共就可以使用5.5个小时没有一点浪费。现在已知电池的数量和电池能够使用的时间请你找一种方案使得使用时间尽可能的长。输入格式输入包含多组数据。每组数据包括两行第一行是一个整数N(2≤N≤1000)表示电池的数目接下来一行是N个正整数表示电池能使用的时间。输出格式对每组数据输出一行表示电池能使用的时间保留到小数点后1位。样例输入23 533 3 5样例输出3.05.5#include bits/stdc.h using namespace std; int n; int a[10010]; int main() { int t; cint; while(t--) { int sum 0,ma -999999999; cinn; for(int i 1;in;i) { cina[i]; sum a[i]; ma max(ma,a[i]); } sum - ma; if(masum) coutfixedsetprecision(1)(sum*1.0)endl; else coutfixedsetprecision(1)(sum*1.0ma*1.0)/2endl; } return 0; }书架题目描述John最近买了一个书架用来存放奶牛养殖书籍但书架很快被存满了只剩最顶层有空余。John共有N头奶牛(1≤N≤20,000)每头奶牛有自己的高度Hi(1≤Hi≤10,000),N头奶牛的总高度为S。书架高度B(1≤B≤S2,000,000,007).为了到达书架顶层奶牛可以踩着其他奶牛的背像叠罗汉一样直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了帮助John到达书架顶层找出使用奶牛数目最少的解决方案吧。输入格式第1行:空格隔开的整数N和B。第2~N1行:第i1行为整数Hi。输出格式能达到书架高度所使用奶牛的最少数目。输入样例6 4061811131911输出样例3#include bits/stdc.h using namespace std; int n,m; int a[20010]; bool cmp(int x,int y) { return xy; } int main() { cinnm; for(int i 1;in;i) { cina[i]; } sort(a1,an1,cmp); int cnt 0; int sum 0; for(int i 1;in;i) { sum a[i]; cnt; if(summ) break; } coutcnt; return 0; }师傅加工零件题目描述某工厂有n个零件加工的师傅每位师傅每天能够加工出不同数量的零件。现有m个零件要求一天加工完请问该工厂最少需要派几个师傅来完成这次零件加工任务如果安排所有的师傅都参与加工也不能在一天内完成任务请输出“NO”。输入格式第一行有两个整数用空格隔开;第一个整数代表要加工的总零件个数m(m10^6)第二个整数代表工厂的零件加工师傅的数量n(n100)。第二行有n个整数分别代表每个师傅每天能够加工出来的零件数量(每个师傅每天加工的零件数量10^4)。输出格式工厂在1天时间内加工所有零件需要的师傅数量或者输出NO。样例输入复制10 51 3 2 4 2输出复制4#include bits/stdc.h using namespace std; int n,m; int a[20010]; bool cmp(int x,int y) { return xy; } int main() { cinmn; for(int i 1;in;i) { cina[i]; } sort(a1,an1,cmp); int cnt 0; int sum 0; for(int i 1;in;i) { sum a[i]; cnt; if(summ) break; } coutcnt; return 0; }