题目描述

地址 https://algospot.com/judge/problem/read/LUNCHBOX

算法1

解法 贪心算法

主要考虑是以加热时间为切入点还是吃法时间为切入点

由于加热时间肯定是紧凑的一个接着一个 总时间是不会改变的

而吃饭时间将吃饭时间长的优先考虑 可以节约时间

尝试将吃饭时间长的便当优先加热

最后的答案是 某个便当加热后加上吃该便当的时间的和 。(只要加热完 便当可以同时吃，所以取便当加热完加上吃的时间的最大值)

C++ 代码

// 1231.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>


using namespace std;

/*
//==================================
2
3
2 2 2
2 2 2
3
1 2 3
1 2 1
//==========================================
8
7
*/

int loop;

int n;


const int N = 100010;
int a[N];
int m[N];

vector<pair<int, int>> vp;

void solve()
{
    int ans = 0;
    int beginEat = 0;
    for (int i = 0; i < n; i++) {
        beginEat += vp[i].first;
        ans = max(ans, beginEat + vp[i].second);
    }
    cout << ans << endl;
}

bool cmp(const pair<int, int>&a, const pair<int, int>& b) {
    if (a.second > b.second) return true;
    else if (a.second == b.second) {
        return a.first > b.first;
    }

    return false;
}


int main()
{
    cin >> loop;

    while (loop--) {
        memset(a, 0, sizeof(a));
        memset(m, 0, sizeof(m));
        vp.clear();
        cin >> n;

        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> m[i];
        }
        for (int i = 0; i < n; i++) {
            vp.push_back({a[i],m[i]});
        }
        sort(vp.begin(), vp.end(), cmp);

        solve();
    }


    return 0;
}