算法课第三次作业

1、书面作业

懒得将 latex 转成 markdown了，直接传个PDF得了。

5、Cross the river

贪心的基本思想：最重的人和最轻的人如果不超载重，就一起过河，如何超重，就最重的人自己一条船单独过河。

#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>

using namespace std;
int main(){

    int n,l;
    int weight[50005];
    cin >> n >> l;
    for( int i=0; i<n; i++ ){
        scanf("%d",weight+i);
    }
    sort(weight,weight+n);
    int ans = 0, left = 0, right = n-1;
    while( left<=right ){
        ans++;
        if( weight[right]+weight[left] <= l ){
            left++;
            right--;
        }
        else{
            right--;
        }
    }
    cout << ans << endl;
    return 0;
}

6、Assign banana to monkeys

贪心的基本思路：先按照位置排序，位于第 i 个位置的猴子就拿第 i 个位置的香蕉就好。

#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

int monkey[5000005];
int banana[5000005];

int main(){
    int n=0;
    char ch;
    do{
        scanf("%d",monkey+n);
        n++;
    }while( (ch=getchar())!='\n' );
    sort(monkey, monkey+n);

    n=0;
    do{
        scanf("%d",banana+n);
        n++;
    }while( (ch=getchar())!='\n' );
    sort( banana, banana+n );
    int ans = 0;
    for( int i=0; i<n; i++ ){
        ans = max( ans, abs(monkey[i] - banana[i]) );
    }
    cout << ans << endl;
    return 0;
}