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;
}

 凑零钱

 雷达安装