貪心算法作業參考：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;
}