实验三：贪心

1.减肥的小k1

题目描述

小K没事干，他要搬砖头，为了达到较好的减肥效果，教练规定的方式很特别：
每一次，小K可以把两堆砖头合并到一起，消耗的体力等于两堆砖头的重量之和。

经过 n-1次合并后， 就只剩下一堆了。小K在搬砖头时总共消耗的体力等于每次合并所耗体力之和。小K为了偷懒，希望耗费的体力最小。

例如有 3堆砖头，数目依次为 1、2、9 。可以先将 1 、 2 堆合并，新堆数目为3 ，耗费体力为 3 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12 ，耗费体力为12 。所以总共耗费体力 =3+12=15。可以证明 15为最小的体力耗费值。

输入要求

共两行。

第一行是一个整数 n(1≤n≤1000) ，表示砖头堆数。

第二行n个整数，每个整数表示每堆砖头的砖头块数。

输出要求

一个整数，也就是最小的体力耗费值。

输入样例

3
1 2 9

输出样例

15

这个问题很简单，只需要每次挑两个最小的加到sum里，再将两个数之和放回到数组中，并使得数组有序，操作n-1次之后就得到了想要的解。

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,a[1000],sum=0,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

#include<bits/stdc++.h>
using namespace std;
int a[501]={0},ct=0;//ct表示跳跃的次数
int jump(int i,int len)
{int k,j=0,l,max=0;// 已经退出了if(i>=len-1) return 0;// 还要继续跳k=a[i];ct++;// 再向前跳k步可以跳出范围if(i+k>=len-1) return 0;// 找出未来a[i]个元素中能跳到的最远距离for(l=i+1;l<=i+k;l++){// 设置一个max用于记录能跳到的最大距离// 如果在位置 l 跳长度为 a[l] 的距离，到达 l+a[l]// 如果 l+a[l] > max 就将下一个落点设置到 j=l 处// 按此方法，每次都跳到该区间中能到达的最远位置，就能得到最优解if(max<=l+a[l]){//更新数据j=l;max=l+a[l];}}jump(j,len); //跳到最远的数组里
}
int main()
{int x,len,i=0;while(cin>>x){a[i++] = x;}len = i;//len表示数组长度jump(0,len);cout<<ct<<endl;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

输入区间，按照区间左端点将区间进行排序，左端点相同的区间按照右端点排序。

在给定的区间内找到最小值和最大值作为做起点和终点。

初始右区间设定为起点，左区间设定为起点。

#include<bits/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,cnt=0;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-B+l。
居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

输入要求

第一行包含数据N，区域的个数；

第二行包含H，房子的数目；

下面的H行描述居民们的需要:B E T。

输出要求

输出能满足所有要求的最少的树的数。

输入样例

9

4

1 4 2

4 6 2

8 9 2

3 5 2

输出样例

5

#include<iostream>
#include<algorithm>
using namespace std;struct request
{//定义一个结构体来存储居民的需求int B,E,T;//B:左端点，E：右端点，T：需要种的树的数量
}a[500];
bool cmp(request a,request b)
{if(a.E==b.E)return a.B<b.B;return a.E<b.E;
}
int main()
{int B,E,T;int N,H;cin>>N>>H;for(int i=1;i<=H;i++){cin>>a[i].B>>a[i].E>>a[i].T;}sort(a+1,a+1+H,cmp);//按照右端点的大小对需求进行排序int num=0;//num表示树的总数int road[10000]={0};//用road数组记录道路上是否已经种树for(int i=1;i<=H;i++)//遍历每一条需求{int ans=0;for(int j=a[i].B;j<=a[i].E;j++)ans+=road[j];//ans表示B到E已经种了多少棵树for(int j=a[i].E;j>=a[i].B&&ans<a[i].T;j--)//尽量从右开始种树 {if(!road[j])//如果tr[j]的位置上还没被种树的话，种树 {road[j]=1;ans++;num++;}}}cout<<num<<endl;return 0;
}