网上书店网网站建设,网页设计与制作黑马程序员,专业建站源码,一个帮你赚钱的网站是谁做的广告1.减肥的小k1
题目描述
小K没事干#xff0c;他要搬砖头#xff0c;为了达到较好的减肥效果#xff0c;教练规定的方式很特别#xff1a; 每一次#xff0c;小K可以把两堆砖头合并到一起#xff0c;消耗的体力等于两堆砖头的重量之和。
经过 n-1次合并后#xff0c; …1.减肥的小k1
题目描述
小K没事干他要搬砖头为了达到较好的减肥效果教练规定的方式很特别 每一次小K可以把两堆砖头合并到一起消耗的体力等于两堆砖头的重量之和。
经过 n-1次合并后 就只剩下一堆了。小K在搬砖头时总共消耗的体力等于每次合并所耗体力之和。小K为了偷懒希望耗费的体力最小。
例如有 3堆砖头数目依次为 1、2、9 。可以先将 1 、 2 堆合并新堆数目为3 耗费体力为 3 。接着将新堆与原先的第三堆合并又得到新的堆数目为 12 耗费体力为12 。所以总共耗费体力 31215。可以证明 15为最小的体力耗费值。
输入要求
共两行。
第一行是一个整数 n(1≤n≤1000) 表示砖头堆数。
第二行n个整数每个整数表示每堆砖头的砖头块数。
输出要求
一个整数也就是最小的体力耗费值。
输入样例
3 1 2 9
输出样例
15
这个问题很简单只需要每次挑两个最小的加到sum里再将两个数之和放回到数组中并使得数组有序操作n-1次之后就得到了想要的解。
#includebits/stdc.h
using namespace std;
int main()
{int n,a[1000],sum0,i;cin n;for ( i 0; i n; i){cin a[i];}sort(a, a n);// 计算两个最小数之和加入到sum中并且放回到原数组中使其有序for ( i 0; i n - 1; i) {int temp a[i 1] a[i];//记录前两个最小的值int k i 2;//k为第三个的下标// 找到一个合适的位置放置 tempwhile (a[k] temp k n){// 比较第三个和前两个的和若第三个比前两个要小// 这里 a[k-1]是无效位因为已经将a[k-1]和a[k-2]的值赋给了temp可以随意覆盖。a[k - 1] a[k];//前移k;}// 找到正确的位置将数字放入该位置a[k - 1] temp;sum temp;}cout sum endl;return 0;
}2.最小跳数
题目描述
给定一个非负整数数组假定你的初始位置为数组第一个位置。数组中的每个元素代表你在那个位置能够跳跃的最大长度。你的目标是到达最后一个下标位置并且使用最少的跳跃次数。
输入要求
输入一组非负整数数组数组长度不超过500。
输出要求
最少经过几次跳跃可以到达最后一个位置。
输入样例
2 3 1 1 4
输出样例
2
#includebits/stdc.h
using namespace std;
int a[501]{0},ct0;//ct表示跳跃的次数
int jump(int i,int len)
{int k,j0,l,max0;// 已经退出了if(ilen-1) return 0;// 还要继续跳ka[i];ct;// 再向前跳k步可以跳出范围if(iklen-1) return 0;// 找出未来a[i]个元素中能跳到的最远距离for(li1;lik;l){// 设置一个max用于记录能跳到的最大距离// 如果在位置 l 跳长度为 a[l] 的距离到达 la[l]// 如果 la[l] max 就将下一个落点设置到 jl 处// 按此方法每次都跳到该区间中能到达的最远位置就能得到最优解if(maxla[l]){//更新数据jl;maxla[l];}}jump(j,len); //跳到最远的数组里
}
int main()
{int x,len,i0;while(cinx){a[i] x;}len i;//len表示数组长度jump(0,len);coutctendl;return 0;
}3.区间问题
题目描述
给出n个区间的起点和终点求最少使用其中多少个区间可以将所有区间所在的区域完全覆盖。测试的数据确保这1点。
输入要求
第1行一个整数n表示n个区间
第2行开始n行每行2个整数表示一个区间范围。
类似[1,4][5,6]被认为是覆盖了[1,6]。
输出要求
从起点开始按区间先后顺序输出选中的区间。所选的区间应尽可能向终点扩展。
输入样例
7 1 5 1 6 3 6 1 7 6 9 9 10 7 9
输出样例
1 7 6 9 9 10
输入区间按照区间左端点将区间进行排序左端点相同的区间按照右端点排序。
在给定的区间内找到最小值和最大值作为做起点和终点。
初始右区间设定为起点左区间设定为起点。
#includebits/stdc.h
using namespace std;
struct Area
{int left, right;
}area[100],r[100];
// 定义比较区间大小的规则
bool cmp(Area a,Area b)
{if (a.left b.left)return true;else if (a.left b.left a.right b.right)return true;else return false;
}
int main()
{// 初始化int n,i,cnt0;cin n;for ( i 0; i n; i) {cin area[i].left area[i].right;}// 排序sort(area, area n, cmp);int right area[0].left - 1;// 初始的右端点int end area[n - 1].right;// 终点// 遍历每个区间段更新右端点的范围for (i 0; i n-1;) {int max_right area[i].right;// 定义能得到的最大右端点int max_index i;while (area[i].left right 1 i n){// 该区间左边小于当前的右端点,1 这种情况代表两个区间是紧挨着的if (area[i].right max_right){max_right area[i].right;//记录能到达的最大的右端点的值max_index i;//记录能到达的最大的右端点的区间编号}i;}// 这里每次循环的右端点是受限的只有一小部分区间会参与// 随着右端点的右移算法不断接近最优解right max_right;//更新右的值r[cnt] area[max_index];//数组中记录被选择的区间i max_index;if (right end) break;//嘿嘿终于到终点啦~~结束}for (i 0; i cnt; i){cout r[i].left r[i].right endl;}return 0;
}4.种树
题目描述
一条街的一边有几座房子。因为环保原因居民想要在路边种些树路边的地区被分割成块并被编号成1…N 每个部分为一个单位尺寸大小并最多可种一棵树每个居民想在门前种些树并指定了三个号码B,E,T这三个数表示该居民想在B和E之间最少种T棵树。 当然B≤E,居民必须记住在指定区不能种多于区域地块数的树所以T≤E-Bl。 居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。
输入要求
第一行包含数据N区域的个数
第二行包含H房子的数目
下面的H行描述居民们的需要:B E T。
输出要求
输出能满足所有要求的最少的树的数。
输入样例
9
4
1 4 2
4 6 2
8 9 2
3 5 2
输出样例
5
#includeiostream
#includealgorithm
using namespace std;struct request
{//定义一个结构体来存储居民的需求int B,E,T;//B:左端点E右端点T需要种的树的数量
}a[500];
bool cmp(request a,request b)
{if(a.Eb.E)return a.Bb.B;return a.Eb.E;
}
int main()
{int B,E,T;int N,H;cinNH;for(int i1;iH;i){cina[i].Ba[i].Ea[i].T;}sort(a1,a1H,cmp);//按照右端点的大小对需求进行排序int num0;//num表示树的总数int road[10000]{0};//用road数组记录道路上是否已经种树for(int i1;iH;i)//遍历每一条需求{int ans0;for(int ja[i].B;ja[i].E;j)ansroad[j];//ans表示B到E已经种了多少棵树for(int ja[i].E;ja[i].Bansa[i].T;j--)//尽量从右开始种树 {if(!road[j])//如果tr[j]的位置上还没被种树的话种树 {road[j]1;ans;num;}}}coutnumendl;return 0;
}
