前言

简介：涉及贪心算法，题目源于洛谷 建议大家先自行尝试解题，同时阿鑫的水平不高，所以题解也通常并不算好，建议大家可以在洛谷相关题目的题解处查看其他大佬的题解，阿鑫的题解简单看看就好。

所谓贪心算法，不考虑整体，每次只做当前情况最优解。所以其并不适用所有题，在用前应证明其贪心的正确和可行性。

练习

洛谷P5019 [NOIP2018 提高组] 铺设道路

题目链接：洛谷P5019 [NOIP2018 提高组] 铺设道路

题目描述
春春是一名道路工程师，负责铺设一条长度为 n 的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区域，一开始，第 i 块区域下陷的深度为 d_i 。
春春每天可以选择一段连续区间 [L,R]，填充这段区间中的每块区域，让其下陷深度减少 1。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 0 。
春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 0 。
输入格式
输入文件包含两行，第一行包含一个整数 n，表示道路的长度。 第二行包含 n 个整数，相邻两数间用一个空格隔开，第 i 个整数为 d_i 。
输出格式
输出文件仅包含一个整数，即最少需要多少天才能完成任务。
输入输出样例
输入
6
4 3 2 5 3 5
输出
9
说明/提示
【样例解释】
一种可行的最佳方案是，依次选择： [1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。
【数据规模与约定】
对于 30% 的数据，1 ≤ n ≤ 10 ；
对于 70% 的数据，1 ≤ n ≤ 1000 ；
对于 100% 的数据，1 ≤ n ≤ 100000 , 0 ≤ d_i ≤ 10000 。

解题思路

如果只有一个坑（深度为d_x），那么只需要填d_x天。（sum=d_x）</br>

如果其后面还有一个坑（深度为d_x+1），</br>

如果d_x+1≤ d_x则在填d_x时顺便填完d_x+1。(sum=sum)</br>

如果d_x+1> d_x,则还需要d_x+1-d_x天。(sum=sum+d_x+1-d_x)</br>

ac题解

//时间:63ms(O2:60ms)  内存:1.08MB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
long long a[MAXN];
long long sum=0;
int n;

int main()
{
    cin>>n;
    int i,j;    
    for(i=1;i<=n;i++) cin>>a[i];

    sum=a[1];
    for(i=1;i<n;i++){
        if(a[i+1]>a[i]){
            sum+=(a[i+1]-a[i]);
        }
    }

    cout<<sum<<endl;
    return 0;
 }

洛谷P1080 [NOIP2012 提高组] 国王游戏

题目链接：洛谷P1080 [NOIP2012 提高组] 国王游戏

题目描述
恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
输入格式
第一行包含一个整数 n，表示大臣的人数。
第二行包含两个整数 a和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
输出格式
一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
输入输出样例
输入
3
1 1
2 3
7 4
4 6
输出
2
说明/提示
【输入输出样例说明】
按 1、2、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 1、3、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按 2、1、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按2、3、1这样排列队伍，获得奖赏最多的大臣所获得金币数为 9；
按 3、1、2这样排列队伍，获得奖赏最多的大臣所获得金币数为 2；
按3、2、1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9。
因此，奖赏最多的大臣最少获得 2 个金币，答案输出 2。
【数据范围】
对于 20% 的数据，有 1≤ n≤ 10,0 < a,b < 8；
对于 40% 的数据，有1≤ n≤20,0 < a,b < 8；
对于 60% 的数据，有 1≤ n≤100；
对于 60% 的数据，保证答案不超过 10⁹；
对于 100% 的数据，有 1 ≤ n ≤1,000,0 < a,b < 10000。
NOIP 2012 提高组 第一天 第二题

解题思路

ac题解

//时间：260ms(O2:101ms)  内存:856.00KB
#include <bits/stdc++.h>
using namespace std;

int n;
string ans="",t;
//高精度除低精度
string highPrecisionDivision(string a,int b){
    string ans="";
    long long t=0;
    int flag=0;        //flag==1时开始记录答案，因为前面都不够除，无需补零
    for(int i=0;i<a.length();i++){
        t=t*10+(a[i]-'0');
        if(t/b)flag=1;    
        if(flag){
            ans+=(t/b)+'0';
        }
        t%=b;
    }
    if(ans!="")return ans;
    else return "0";
}
//高精度乘低精度
string highPrecisionMultiplication(string a,int b){    
    string ans;
    long long t=0;
    reverse(a.begin(),a.end());    //反转字符串方便计算,下同
    for(int i=0;i<a.length();i++){
        t+=(a[i]-'0')*b;
        ans+=t%10+'0';
        t/=10;
    }
    while(t){
        ans+=t%10+'0';
        t/=10;
    }
    reverse(ans.begin(),ans.end());
    //去除前面多余的0,同时保证不会全删掉（可以输出 0） 
    while(ans[0]=='0'&&ans.length()>1) ans.erase(ans.begin()); 
    return ans;
}
string smax(string a,string b){
    if(a.length()>b.length()) return a;
    else if(a.length()<b.length()) return b;
    else if(a>=b)return a;
    else return b;
}
struct p{
    int l;
    int r;
}a[1005];

int mycmp(p a,p b){
    return (a.l*a.r)<(b.l*b.r);
}

int main()
{
    cin>>n>>a[0].l>>a[0].r;
    int i;
    for(i=1;i<=n;i++){
        scanf("%d%d",&a[i].l,&a[i].r);
    }
    sort(a+1,a+n+1,mycmp);
    int tt=a[0].l;
    while(tt){
        t+=tt%10+'0';
        tt/=10;
    }
    reverse(t.begin(),t.end());
    for(i=1;i<=n;i++){
        ans=smax(ans,highPrecisionDivision(t,a[i].r));
        t=highPrecisionMultiplication(t,a[i].l); 
    }
    cout<<ans<<endl;
    return 0;
}