Problem

11/11

Schneewittchen und N Zwerge

Problem

«Nun, keine Zwerge, sondern eine Bestrafung!», – dachte Schneewittchen, als er noch einmal versuchte, die Zwerge ins Bett zu bringen. Du wirst einen legen, der andere ist bereits wach! Und so die ganze Nacht.
 
Schneewittchen hat n Zwerge, und sie sind alle sehr unterschiedlich. Sie weiß, dass es ai Minuten braucht, um den i-ten Zwerg ins Bett zu legen, und danach wird er genau bi Minuten schlafen. Hilf Schneewittchen herauszufinden, ob sie mindestens eine Minute Ruhe bekommen kann, wenn alle Zwerge schlafen, und wenn ja, in welcher Reihenfolge sie die Zwerge zum Schlafen bringen müssen.
 
Lassen Sie zum Beispiel nur zwei Zwerge essen, a1 = 1, b1 = 10, a2 = 10, b2 = 20. Wenn Schneewittchen zuerst anfängt, den ersten Zwerg zu legen, dauert es dann ganze 10 Minuten, um den zweiten zu legen, und während dieser Zeit wird der erste aufwachen. Wenn sie mit dem zweiten Zwerg beginnt, hat sie dann Zeit, den ersten zu legen und bekommt so viele wie 10 Minuten Ruhe.
 
Eingaben
Die erste Zeile der Eingabedatei enthält die Zahl n (1 <= n <= 10000), die zweite Zeile enthält die Zahlen a1,a2,… an, die dritte Zeile enthält die Zahlen b1,b2,… bn (1 <= ai, bi <= 100000).
 
Ausgabe
Geben Sie in die Ausgabedatei n Zahlen – die Reihenfolge aus, in der die Zwerge schlafen sollen. Wenn Schneewittchen sich nicht ausruhen kann, geben Sie die Zahl -1 aus.

Eingabe Ausgabe
2
1 10
10 20
 2 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++
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!