Solution UVA: 10026 - Shoemaker's Problem

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10026 - Shoemaker's Problem	Accepted	C++11	0.000	0.000	2433	1 mins ago

Suggest:

- This problem is good to practice your brain for sort and greedy

- You need create a function to compare two value in input

a b

c d
a * d < c * b => (a,b) is smaller than (c,d)

- Exam 1:

1 1000

3 4

1 * 4 < 3 * 1000 => (1,1000) is smaller than (3,4)

- Exam 2:

2 2

3 4

2 * 4 > 3 * 2 => (3,4) is smaller than (2,2)

#include<bits/stdc++.h>

#define X first

#define Y second

using namespace std;

typedef pair<int, pair<int, int>> ii;

ii a[1000111];

bool comp(ii t, ii f){

    if (t.X*f.Y.X < f.X*t.Y.X) return true;

    if (t.X*f.Y.X == f.X*t.Y.X)

        return t.Y.Y < f.Y.Y;

    return false;

}

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    int kase;   cin >> kase;

    while(kase--){

        int n;  cin >> n;

        for(int i=1; i<=n; i++){

            int x, y;   cin >> x >> y;

            a[i]= ii(x, {y,i});

        }

        sort(a+1, a+1+n, comp);

       

        for(int i=1; i<=n; i++) cout<<a[i].Y.Y<<(i==n?"\n":" ");    

        if (kase) cout<<"\n";

    }

}