C++U4-02-贪心算法2

【算法分析】
贪心算法：先对数组从小到大排序，用 l=1, r=n 指针指向首尾元素；如果 pl+pr≤w，则将pl和pr分一组，指针 l++,r--。如果 pl+pr>w，则将 pr单独作为一组，指针 r--。如此反复直到取完所有元素。

#include <iostream>
#include <algorithm>
using namespace std;

int w, n, ans;
int p[30010];

int main() {
    cin >> w >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    int l = 1, r = n; //左右指针，指向首尾元素
    sort(p + 1, p + n + 1);
    while (l <= r) {
        if (p[l] + p[r] <= w) { //物品i和物品j分一组 
            l++;
            r--;
            ans++;
        }
        else {  //物品j单独一组 
            r--;
            ans++;
        }
    }
    cout << ans;
    return 0;
}

【算法分析】
当只有两个活动（两个时间段）的时候，选择参加哪个都是可以的，当有第三个活动的时候，这时候就会发现优先选择前两个结束较早的那个活动，才能完整的看第三个活动，所以尽早看完一个活动就有机会参加其它活动（也就是按结束时间从早到晚排序）。

#include <iostream>
#include <algorithm>
using namespace std;

struct node {
    int s, e;//开始时间，结束时间
}a[1010]; 

bool cmp(node a, node b) {
    return a.e < b.e;
}

int main() {
    int n, num = 1;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i].s >> a[i].e;
    sort(a, a + n, cmp);
    int last = a[0].e;
    for (int i = 1; i < n; i++) {
        if (a[i].s >= last) { //下一个活动的开始时间大于等于下一个活动的结束时间
            num++;
            last = a[i].e;
        }
    }
    cout << num;
    return 0;
}

【算法分析】
本题的贪心需要预处理下，定义结构体 Pos 存当前位置和当前位置能隔开的对数，开 2 个结构体一维数组，row[i].num 记录如果在第 i 行加通道,可以分割多少对调皮学生,col[j].num 记录如果在第 j 列加通道,可以分割多少对调皮学生。然后用 sort 排序，隔开对数多的放在前面，在此前提下，位置小的排到前面（输出的结果也要排序）。最后输出分割学生最多的前 k 行和前 l 列。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e3 + 10;
struct Pos {
    int pos, num;  // 位置，隔开的对数 
} row[N], col[N];  // 横向通道，纵向通道 

bool cmp1(Pos a, Pos b) {
    return a.num > b.num;  // 隔开对数多的放前面 
}

bool cmp2(Pos a, Pos b) {
    return a.pos < b.pos;  // 位置小的排在前面 
}

int main() {
    int m, n, k, l, d;  // m 行 n 列的教室，k 个横向通道，l 个纵向通道，d 对交头接耳的同学 
    cin >> m >> n >> k >> l >> d;
    for(int i = 1; i <= d; i++) {
        int x1, y1, x2, y2;  // 会交头接耳的两个同学的位置
        cin >> x1 >> y1 >> x2 >> y2;
        if(y1 == y2) {  // 同一列 
            int x = min(x1, x2);
            row[x].pos = x;
            row[x].num++;  // x 这条横向通道能隔开的对数加 1 
        }else if(x1 == x2) {  // 同一行 
            int y = min(y1, y2);
            col[y].pos = y;
            col[y].num++;  // y 这条纵向通道能隔开的对数加 1 
        } 
    }
    sort(row + 1, row + m, cmp1);  // 1~m-1 
    sort(col + 1, col + n, cmp1);  // 1~n-1 
    sort(row + 1, row + k + 1, cmp2);  // 1~k 按照位置升序 
    sort(col + 1, col + l + 1, cmp2);  // 1~l 按照位置升序 
    for(int i = 1; i <= k; i++) {
        cout << row[i].pos << " ";
    } 
    cout << endl;
    for(int i = 1; i <= l; i++) {
        cout << col[i].pos << " ";
    }
    return 0;
}