入门篇2——算法初步（4.4贪心）

贪心：考虑在当前状态下局部最优的策略，从而达到全局最优（不一定）。
区间贪心：先选择左端点最大或右端点最小的区间
题目情况：3道简单题，3道难题
b1023：略
b1020/a1070：略
a1033：
1）优先前往更低油价的加油站。在满油状态下，如果第一次出现更便宜的加油站，就加恰好能够到达这个加油站的油量。
2）如果没有，判断能否到达终点。如果不能，优先前往满油状态下最远的加油站。
3）如果没有2）所需的加油站，则不能到达终点。

#include
using namespace std;
struct node {
    double p;
    double d;
}a[510];
bool cmp(node e, node f) {
    return e.d < f.d;
}
int main() {
    double c, fin, davg;
    int n;
    scanf("%lf%lf%lf%d", &c, &fin, &davg, &n);
    for (int i = 0; i < n; i++) {
        scanf("%lf%lf", &a[i].p, &a[i].d);
    }
    sort(a, a + n, cmp);
    //考虑起点
    if (a[0].d) {
        printf("The maximum travel distance = 0.00n");
        return 0;
    }
    int i = 0;
    double cost = 0, rc = 0;//rc表示剩余油量
    while (i < n) {
        int j = i + 1, flag1 = 0, flag2 = 0;//flag1判断更便宜的，flag2判断有没有加油站
        //判断最大行驶距离内是否有更便宜的加油站或是否有加油站
        while (j < n && a[j].d <= a[i].d + c * davg) {
            flag2 = 1;
            if (a[j].p < a[i].p) {
                flag1 = 1;
                //判断剩余油量是否足够
                double nc = (a[j].d - a[i].d) / davg;//需要的油量
                if (rc >= nc) rc -= nc;
                else cost += (nc - rc) * a[i].p, rc = 0;
                i = j;
                break;
            }
            j++;
        }
        //到达终点
        if (!flag1 && a[i].d + c * davg >= fin) {
            double nc = (fin - a[i].d) / davg;
            if (rc < nc) cost += (nc - rc) * a[i].p;
            printf("%.2lfn", cost);
            break;
        }
        //不能到达终点
        if (!flag2 && a[i].d + c * davg < fin) {
            printf("The maximum travel distance = %.2lfn", a[i].d + c * davg);
            break;
        }
        //没有更便宜的加油站，加满
        if (!flag1) {
            cost += (c - rc) * a[i].p;
            rc = c - (a[j - 1].d - a[i].d) / davg;
            i = j - 1;//i指向最大行驶距离内的最后一个加油站
        }
    }
}

a1037：略
a1067：
1）当0在本位上时，将0和最小的还没有回到本位上的数交换
2）当0不在本位上时，将0和0所处位置的本位数交换

#include
using namespace std;
int pos[100010];//数i的位置
int main() {
    int n;scanf("%d", &n);
    int cnt = 0, left = n - 1;//除0外不在本位上的数的个数
    for (int i = 0; i < n; i++) {
        int num;scanf("%d", &num);
        pos[num] = i;
        if (num && pos[num] == num) left--;//num在本位，个数减一
    }
    int k = 1;//除0以外不在本位上的最小数
    //仍有不在本位上的数时，继续交换
    while (left > 0) {
        if (pos[0] == 0) {//0在本位上，把0从0号位换出去
            while (k < n) {
                if (pos[k] != k) {
                    swap(pos[0], pos[k]);
                    cnt++;
                    break;
                }
                k++;
            }
        }
        if (pos[0] != 0) {//0不在本位上，交换0的位置和该位置本位数的位置
            swap(pos[0], pos[pos[0]]);
            cnt++;
            left--;
        }
    }
    printf("%dn", cnt);
}

a1038：对于c++STL中的string的使用；如果s1+s2

#include
using namespace std;
string str[10010];
bool cmp(string e, string f) {
    return e + f < f + e;// '+'理解为拼接，如果e + f < f + e，e在f前面
}
int main() {
    int n;cin >> n;//string只能用cin、cout输入输出
    for (int i = 0; i < n; i++) {
        cin >> str[i];
    }
    sort(str, str + n, cmp);
    string res;//string默认初始化为空串，res作为拼接的字符串
    for (int i = 0; i < n; i++) {
        res += str[i];
    }
    while (res.length() > 0 && res[0] == '0') {//删除前导零
        res.erase(res.begin());//删除res0号位的字符
    }
    if (res.length() == 0) cout << 0 << endl;//如果结果为空，输出0
    else cout << res << endl;
}