Le problème est le suivant :
Le club de sport le plus prestigieux d'une ville compte exactement N membres. Chacun de ses membres est fort et beau. Plus précisément, i -Le cinquième membre de ce club (les membres étant numérotés selon leur date d'entrée dans le club) a une force S <em>i </em> et la beauté B <em>i </em> . Comme il s'agit d'un club très prestigieux, ses membres sont très riches et donc des personnes extraordinaires, aussi se détestent-ils souvent extrêmement. Strictement parlant, i - cinquième membre du club, M. X déteste j -ème membre du club M. Y si S <em>i </em> S <em>j </em> et B <em>i </em> B <em>j </em> ou si S <em>i </em> S <em>j </em> et B <em>i </em> B <em>j </em> (si les deux propriétés de M. X sont supérieures aux propriétés correspondantes de M. Y, il ne le remarque même pas, en revanche, si ses deux propriétés sont inférieures, il respecte beaucoup M. Y).
Pour célébrer une nouvelle année 2003, l'administration du club prévoit d'organiser une fête. Cependant, ils ont peur que si deux personnes qui se détestent assistent simultanément à la fête, après un verre ou deux, elles se battent. Il ne faut donc pas inviter deux personnes qui se détestent. D'un autre côté, pour maintenir le prestige du club à un niveau approprié, l'administration veut inviter le plus grand nombre de personnes possible.
Étant la seule personne de l'administration qui n'a pas peur de toucher un ordinateur, vous devez écrire un programme qui trouvera qui inviter à la fête.
Entrée
*La première ligne du fichier d'entrée contient le nombre entier N - le nombre de membres du club. ( 2 N 100,000 ). Les N lignes suivantes contiennent chacune deux nombres - S <em>i </em> et B <em>i </em> respectivement ( 1 S <em>i </em> , B <em>i </em> 109 ).*
Sortie
Sur la première ligne du fichier de sortie, imprimez le nombre maximum de personnes qui peuvent être invitées à la fête. Sur la deuxième ligne, affichez N nombres entiers - nombres de membres à inviter dans un ordre arbitraire. Si plusieurs solutions existent, affichez l'une d'entre elles.
Exemple de test(s)
Entrée
4 1 1 1 2 2 1 2 2Sortie
2 1 4
J'essaie de résoudre un problème mais la complexité de mon algorithme est O(N^2) et puisque 2<=N<=100000 il y a un besoin d'améliorer un algorithme. J'ai résolu le problème en utilisant l'algorithme de programmation dynamique de la plus longue sous-séquence croissante qui a une complexité de O(N^2). Quelqu'un a-t-il une idée pour améliorer l'algorithme ?
