Problem

11/11

白雪公主和 N 小矮人

Problem

<分区> “好吧，不是侏儒，而是某种惩罚！”，–白雪公主想，又一次试图让矮人入睡。你会放下一个——对方已经醒了！整晚都是这样。
<分区>  
<分区> 白雪公主有n个小矮人，他们都非常不同。她知道让第 i 个小矮人入睡需要 ai 分钟，之后他会正好睡 bi 分钟。帮助白雪公主找出当所有矮人都睡着时她是否可以至少休息一分钟，如果可以，让矮人入睡的顺序是什么。
<分区>  
<分区> 例如，假设只有两个侏儒，a1 = 1，b1 = 10，a2 = 10，b2 = 20。如果白雪公主先让第一个侏儒上床睡觉，那么她需要 10 分钟才能让第二个侏儒上床睡觉一个人上床睡觉，在此期间第一个会醒来。如果她从第二个小矮人开始，那么她将有时间让第一个小矮人上床休息整整 10 分钟。
<分区>  
<分区> 输入数据
<分区> 输入文件的第一行包含数字 n (1 <= n <= 10000)，第二行包含数字 a1,a2,…一个，第三个——数字 b1,b2,… bn (1 <= ai, bi <= 100000).
<分区>  
<分区> 输出
<分区> 打印到输出文件 n 个数字 –让侏儒上床睡觉的顺序。如果白雪公主没有休息，打印数字-1。

<正文> (c) Grigoriev E., 2018

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
输入 输出
<分区> 2 <分区> 1 10 <分区> 10 20 2 1
Write the program below 
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5;

struct dwarf {
    int a, b, i;
    dwarf() {}
    dwarf(int _a, int _i) {
        this->a = _a;
        this->i = _i;
    }
};

int n;
int k;
int c;
vector<dwarf>dwarfs(N);

bool cmp(dwarf a, dwarf b) {   
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        k += x;
        dwarfs.at(i) = dwarf(x, i + 1);
    }

    for (int i = 0; i < n; i++) {
        cin >> dwarfs.at(i).b;
        if (dwarfs.at(i).b - (k - dwarfs.at(i).a) <= 0)
            c++;
    }

    if (c == n) {
        cout << -1;
        return 0;
    }

    sort(dwarfs.begin(), dwarfs.end(), cmp);

    for (int i = 0; i < n; i++)
        cout << dwarfs.at(i).i << " ";

    return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!