Problem

11/11

سنو وايت والأقزام N

Problem

"حسنًا ، ليس التماثيل ، ولكن نوعًا من العقاب!" ، - فكرت بياض الثلج ، مرة أخرى تحاول أن تجعل الأقزام تنام. سوف تضع واحدة أسفل & ndash؛ الآخر مستيقظ بالفعل! وهكذا طوال الليل.
نبسب ؛
تحتوي بياض الثلج على أقزام n ، وكلها مختلفة تمامًا. إنها تعلم أن وضع القزم الأول على النوم يستغرق ذكاءً عاليًا ، وبعد ذلك سينام بالضبط لمدة دقيقتين. ساعد Snow White في معرفة ما إذا كان بإمكانها الحصول على قسط من الراحة لمدة دقيقة على الأقل عندما يكون جميع الأقزام نائمين ، وإذا كان الأمر كذلك ، فما ترتيب وضع الأقزام في النوم.
نبسب ؛
على سبيل المثال ، لنفترض أن هناك قزمتين فقط ، a1 = 1 ، b1 = 10 ، a2 = 10 ، b2 = 20. إذا بدأت Snow White في وضع أول تمثال للنوم أولاً ، فسوف يستغرق الأمر 10 دقائق لوضع الثاني واحد للنوم ، وخلال هذا الوقت سوف يستيقظ الشخص الأول. إذا بدأت بالقزم الثاني ، فسيكون لديها وقت لوضع الأول في الفراش والحصول على 10 دقائق كاملة من الراحة.
نبسب ؛
إدخال البيانات
يحتوي السطر الأول من ملف الإدخال على الرقم n (1 & lt؛ = n & lt؛ = 10000) ، السطر الثاني يحتوي على الأرقام a1 ، a2 ، & hellip؛ وثالث & -. الأرقام b1 و b2 و hellip ؛ bn (1 & lt؛ = ai، bi & lt؛ = 100000).
نبسب ؛
الإخراج
طباعة إلى ملف الإخراج n أرقام & ndash؛ ترتيب وضع التماثيل في الفراش. إذا فشل بياض الثلج في الراحة ، اطبع الرقم -1.

<الجسم>
أدخل الإخراج
2
1 10
10 20
2 1
(ج) 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!