前言：这是四道同类型的贪心简单题，都是在求最值。思路都是（类比冒泡排序）取两个相邻的元素，且这两个元素交换顺序对其他的元素不产生任何影响，那么只要比较这两个元素谁排前面更符合题目的要求（例如假设A在前更优，看能推出什么条件，需要一些数学思维，数学中的max()，甚至用到数学归纳法与反证法），再推广到所有元素即可

题解15：https://ac.nowcoder.com/acm/contest/20960/1024

AC代码&思路：

#include<iostream>
#include<string>
#include<algorithm>//sort()
using namespace std;
bool comp(string a,string b)
{
    return a+b>b+a;//a和b拼起来的字典序大于b+a，那么a就排前面。因为a+b与b+a同长度，所以就是变相的比较整数a+b与b+a
}
int main()
{
    int n;cin>>n;
    string s[25];//string数组，每个元素都是字符串，并不是在指定string的长度
    for(int i=1;i<=n;i++) {cin>>s[i];}
    sort(s+1,s+n+1,comp);
    for(int i=1;i<=n;i++) {cout<<s[i];}
    
    return 0;
}

题解16：https://ac.nowcoder.com/acm/contest/20960/1028

AC代码&思路：

#include<iostream>
#include<algorithm>
using namespace std;
struct ty
{
    int ntime,over;
}a[100005];
bool comp(const ty &a, const ty &b)
{
    return a.over<b.over;//由比较相邻元素交换顺序的max()数学推导得来
}
int main()
{    
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].ntime>>a[i].over;
    }
    sort(a+1, a+1+n, comp);
    long long cent=0,nowtime=0;//要用long long，因为1e5*1e5=1e10级别>2e9
    for(int i=1; i<=n; i++)
    {
        nowtime+=a[i].ntime;//计算累计时间
        cent=max(cent, nowtime-a[i].over);//一定是要在每一循环比较每个任务扣分的最大值，因为排序是保证最大值最小，而不是保证最大值从小到大排序
    }
    
    cout<<cent;
    
    return 0;
}

题解17：https://ac.nowcoder.com/acm/contest/20960/1029

AC代码&思路：

#include<iostream>
#include<algorithm>
using namespace std;
struct ty
{
    int le,ri;
}a[1010];
bool comp(const ty &a, const ty &b)
{
    return a.le*a.ri<b.le*b.ri;//同题解16由数学推到得来PS：还有一种偏法（这里未使用）只有两个元素，那么分别按照它们两相加和相乘排序，最后输入两种排序方法得到结果的最小值
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1; i<=n+1; i++)
    {
        cin>>a[i].le>>a[i].ri;
    }
    sort(a+2/*不含国王*/, a+2+n/*国王也占了一个位置*/, comp);
    int res=0,lenum=1;
    lenum*=a[1].le;
    for(int i=2; i<=n+1; i++)
    {    
        res=max(res, (int)lenum/a[i].ri);
        lenum*=a[i].le;
    }
    
    cout<<res;
    return 0;
}

题解18：https://ac.nowcoder.com/acm/contest/20960/1030

AC代码&思路：

#include<iostream>
#include<algorithm>
using namespace std;
struct ty
{
    int time,eatspeed;
}a[100005];
bool comp(const ty &a, const ty &b)
{
    return a.time*b.eatspeed< b.time*a.eatspeed;//比较前后两元素交换后，两元素花朵损失量相加的最小值得来
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i].time>>a[i].eatspeed;
    }
    sort(a+1,a+1+n,comp);
    long long nowtime=0,eatsum=0;
    for(int i=1; i<=n; i++)
    {
        eatsum+=nowtime*a[i].eatspeed;
        nowtime+=2*a[i].time;//别忘了*2
    }
    
    cout<<eatsum;
    
    return 0;
}