贪心算法作业参考：P1106，P4995，P5019

贪心算法作业参考：P1106，P4995，P5019

P1106 删数问题

作业批注： 原作业提交，是删除k个最大的数。 不一定是删除最大的数。

参考如下，用例：
输入：

50074897
2

输出：

4897

//string erase函数，erase(i,n),从i开始连续删除n个
//每一次找高峰，删掉最坏数，高峰的数一定比后面的数差，因此删掉
#include <bits/stdc++.h>using namespace std;const int N = 255;string num_str;int main()
{int k;cin>>num_str>>k;while(k--){int x=0;// 如果当前的数比后一个小，则x指针一直下移while(num_str[x]<=num_str[x+1]&&x<num_str.size()) x++;// 发现后一个比前一个大下标x，则删除当前数。 即每次删除高峰数。 贪心算法。num_str.erase(x,1);}// 如果，处理结果首位是0， 则把零去除while(num_str[0]=='0'&&num_str.size()>1) num_str.erase(0,1);cout<<num_str;return 0;
}

P4995 跳跳！

#include <bits/stdc++.h>
using namespace std;typedef unsigned long long ull;
const int N = 310;int n;
int a[N];int main(){cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}//从小到大进行排序sort(a+1, a+1+n);//第1次跳的是最高位置ull ans = a[n] * a[n];  int i = 1, j = n;while (i < j){//跳到最低位置ans += (a[j] - a[i]) * (a[j] - a[i]);  //跳到没调的地方中最高的j --;  //最低的位置跳到最高位置ans += (a[i] - a[j]) * (a[i] - a[j]);  i ++;}cout << ans;return 0;
}

P5019 [NOIP 2018 提高组] 铺设道路

用例：

5
6 6 8 9 7

9

以上结果解释： 修筑路段，以及当天后剩余待处理的深度
[1,5] 5 5 7 8 6
[1,5] 4 4 6 7 5
[1,5] 3 3 5 6 4
[1,5] 2 2 4 5 3
[1,5] 1 1 3 4 2
[1,5] 0 0 2 3 1
[3,5] 0 0 1 2 0
[3,4] 0 0 0 1 0
[4,4] 0 0 0 0 0

// 贪心规律，第一段为至少的天数，以后每高一个深度算一天，及时断开的，后面深度差需要单独按天处理#include <bits/stdc++.h>
using namespace std;
int a[100005];
long long ans,n;
int main()
{cin >> n;// 从1下标开始到nfor(int i=1;i<=n;i++)cin >> a[i];// 初始化，ans为第一段的深度处理天数。即至少处理第一段深度的天数ans = a[1];for(int i=2;i<=n;i++)if(a[i]>a[i-1])ans+=a[i]-a[i-1];cout << ans;return 0;
}