11035: 【原1035】二哥炒股票

题目

题目描述

author: 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1035

Description

二哥最近关注了 N 支股票，编号为 1 至 N 。他不断记录下这 N 支股票的股价变动情况。在此期间，他也想知道其中股价第 i 高的是哪支。你能为他快速回答这这样的问题吗？

Input Format

第一行一个整数 N

第二行 N 个整数，第 i 个数表示编号为 i 的股票的初始股价

第三行一个整数 K

接下来 K 行，每行为一条股价变动记录或一条询问：

M x y 表示编号为 x 的股票的股价变成了 y。

Q r a1 a2 ... ar 表示二哥依次询问第 a1 大，第 a2 大...第 ar 大的股票编号为多少。若有不同股票的股价相同，那么令编号小的股票更大。

Output Format

对于每个询问，输出一行 r 个整数，第 i 个整数表示股价第 ai 大的股票编号为多少。这些整数之间用一个空格隔开。

Sample Input

6
1 2 3 4 5 6
5
Q 3 1 3 5
M 1 7
Q 3 1 3 5
M 2 5
Q 3 1 3 5

Sample Output

6 4 2
1 5 3
1 2 4

说明

对于每个询问，都有 \( r \leq 1000 \) ，询问指令数量不超过 10 条

所有股价都不超过 \( 10^5 \)

40%的数据 \( 3 \leq N,K \leq 100 \)

70%的数据 \( 3 \leq N,K \leq 5000 \)

100%的数据 \( 3 \leq N,K \leq 20000 \)

FineArtz's solution

/* 二哥炒股票 */
#include <iostream>
#include <algorithm>
using namespace std;

class Stroke{
public:
    bool operator <(const Stroke &s){
        return (price < s.price || price == s.price && ind > s.ind);
    }

    int ind = 0, price = 0;
};

Stroke a[20005];
int n, k;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i){
        a[i].ind = i;
        cin >> a[i].price;
    }
    cin >> k;
    while (k--){
        char ch;
        cin >> ch;
        if (ch == 'Q'){
            Stroke b[20005];
            for (int i = 1; i <= n; ++i){
                b[i] = a[i];
            }
            sort(b + 1, b + n + 1);
            int r;
            cin >> r;
            while (r--){
                int t;
                cin >> t;
                cout << b[n - t + 1].ind << ' ';
            }
            cout << '\n';
        }
        else{
            int x, y;
            cin >> x >> y;
            a[x].price = y;
        }
    }
    return 0;
}

yyong119's solution

// #include <iostream>
// #include <algorithm>
// using namespace std;
// #define number first
// #define price second
// const int SIZE = 21000;
// int byNumberprice_to_modify[SIZE], stockNumber, commandNumber, numberToModify, priceToModify;
// pair<int, int> byRanking[SIZE];
// bool Cmp(const pair<int, int> & stock1, const pair<int, int> & stock2) {
//  if(stock1.price == stock2.price)
//      return (stock1.number < stock2.number);
//  return (stock1.price > stock2.price);
// }
// int main(){
//  ios::sync_with_stdio(false);
//  cin >> stockNumber;
//  for(int i = 0; i < stockNumber; ++i)
//      cin >> byNumberprice_to_modify[i];
//  cin >> commandNumber;
//  char command;
//  for(int i = 0; i < commandNumber; ++i) {
//      cin >>command;
//      if(command == 'M') {
//          cin >> numberToModify>> priceToModify;
//          byNumberprice_to_modify[numberToModify - 1] = priceToModify;
//      }
//      else {
//          for(int i = 0; i < stockNumber; ++i) {
//              byRanking[i].number = i;
//              byRanking[i].price = byNumberprice_to_modify[i];
//          }
//          sort(byRanking, byRanking + stockNumber, Cmp);
//          int request_number, number_to_cout;
//          cin >> request_number;
//          for(int i = 0; i < request_number; ++i) {
//              cin >> number_to_cout;
//              cout << byRanking[number_to_cout - 1].number + 1 << ' ';
//          }
//          cout << '\n';
//      }
//  }
//  return 0
// }