Module: コンパレータによるソート


Problem

11/11

白雪姫とNの小人たち

Problem

「うーん、ノームじゃなくて、なんらかの罰だ！」, –と白雪姫は考え、またドワーフたちを眠らせようとしました。 1 つ置きます –もう一人はすでに起きています！そして一晩中。
 
白雪姫には n 人の小人がいて、それぞれが大きく異なります。彼女は、i 番目のドワーフを眠らせるのに ai 分かかることを知っています。その後、彼は正確に bi 分眠ります。すべてのドワーフが眠っているときに、白雪姫が少なくとも 1 分間休むことができるかどうか、もしそうなら、どのような順序でドワーフを眠らせるかを白雪姫が見つけるのを手伝ってください。
 
たとえば、ノームが 2 つしかない場合、a1 = 1、b1 = 10、a2 = 10、b2 = 20 とします。白雪姫が最初のノームを最初に寝かせ始めると、2 番目のノームを寝かせるのに 10 分かかります。 1 人が寝て、この間に最初の 1 人が起きます。 2 番目のドワーフから始めると、最初のドワーフを寝かしつけて 10 分間休む時間があります。
 
入力データ
入力ファイルの最初の行には数値 n (1 <= n <= 10000) が含まれ、2 行目には数値 a1、a2、… が含まれます。 an, third –数値 b1,b2,… bn (1 <= ai, bi <= 100000).
 
出力
n 個の番号を出力ファイルに出力 –ノームを寝かせる順番。白雪姫が休めなかった場合は、-1 を出力してください。

<本体> (c) グリゴリエフ 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!