拼多多笔试货运装箱那一题的贪心策略

step1:将货物按重量从小到大排序，将重量大于200的直接装箱
step2:设置左右两个区间游标left和right，接着考虑到100+200这种临界情形，先将right左移到第一个小于200的下标处，将left右移到第一个大于100的下标处，将left~right区间内的货物首尾匹配，如果<=300就装箱，并mark这两个位置已经访问过，如果大于300就不装箱(right这个位置的货物也不装)将right左移一个位置继续匹配直到left == right
step3:在step2的基础上再将100和200重的货物加进来，并将left置0，right置为最后一个货重<=200的货物下标处，首尾匹配，先检验left和right这两个货物是否已mark过，如果mark了就left++或者right--，若都未被标记，当right处货重为100则直接将区间剩余货物一次性3箱这样带走，当right处货重>100时且和重<=300则将left和right处的货物一块装箱带走同时缩进left和right，>300则只能将right处货物装箱带走并缩进right

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

const int maxn = 1005;
int w[maxn];
bool mark[maxn];

int main(){
    int t,n = 0,res = 0;
    while(~scanf("%d",&t)){
        w[n] = t;
        mark[n++] = false;
    }
    sort(w,w+n);
    int left = 0,right = n - 1;
    while(right >= 0 && w[right] > 200){
        res++;
        right--;
    }
    //保存第一个<=200的元素下标
    int nr = right;
    while(right >= 0 && w[right] == 200){
        right--;
    }
    while(left < n && w[left] == 100){
        left++;
    }
    while(left < right){
        if(w[left] + w[right] <= 300){
            res++;
            mark[left] = mark[right] = true;
            left++;
            right--;
        }else{
            right--;
        }
    }
    right = nr;
    left = 0;
    while(left <= right){
        if(mark[left]){
            left++;
        }else if(mark[right]){
            right--;
        }else if(left == right){
            res++;
            break;
        }else if(w[right] == 100){
            int len = right - left + 1;
            res = res + len/3 + (len%3 > 0 ? 1 : 0);
            break;
        }else if(w[left] + w[right] <= 300){
            res++;
            left++;
            right--;
        }else{
            res++;
            right--;
        }
    }
    printf("%d\n",res);
    return 0;
}

#内推##拼多多##笔试题目#