Skip to content

14043: 【原4043】STL系列-algorithm

题目

题目描述

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

Description

面包是一个友善的助教,为了同学们和助教们的身心健康,所以出了这一套C++ STL使用系列,旨在帮助 大家熟悉STL的一些操作。

设你有\(n\)个(0-based)数字,会进行\(m\)此操作,分别如下 1. 将下标为\([i, j)\)间的数从小到大排序。 2. 将下标为\([i, j)\)的数翻转,即第一个数字和最后一个交换位置,第二个和最后第二个交换位置,balabala 3. 输出第\(i\)个到第\(j-1\)个数字,使用空格隔开。 4. 输出下标为\([i, j)\)的数中,最小的一个的数值。 5. 输出下标为\([i, j)\)的数中,大于\(a\)的数的个数。 6. 输出下标为\([i, j)\)的数中,第一个等于\(a\)的数的下标,没有则输出\(j\)。 7. 将下标为\([i, j)\)的数中所有为\(a\)的数都替换成\(b\)。 8. 对于下标为\([i, j)\)的数进行一次划分。对于给定的\(a\),\(b\),\(c\),记\(f=ax^2+bx+c\), 将区间中的数重新排列,使得任意满足\(f(x)>0\)的数在任意不满足的数之前,并且保持原有顺序不变。

对于每一个要求你输出的操作,输出对应的内容。

Input Format

第一行为\(n\)和\(m\), 接下来的\(m\)行为操作,每个操作格式如下, 第一个数字\(t\)表示这个操作的编号,之后是\(i\), \(j\), \(a\) (如果有的话,下同), \(b\), \(c\)

Output Format

对于每一个要求你输出的操作,输出对应的内容。

Sample Input

3 10
56 78 42
8 0 2 -44 -27 -96
5 0 1 48
1 0 0
5 0 1 116
4 0 2
7 0 2 115 25
5 0 1 28
5 0 1 78
3 0 1
3 0 1

Sample Output

1
0
56
1
0
56
56

数据范围

对于100%的数据,\(n \le 5000\),\(m \le 10000\)保证所有数据在整型范围内。

Hint

对自己好一点,这么多东西就不要手写了,调调STL就好啦OvO,基本上所有需要用到的东西都可以在这些里面找到,百行不到就可以写完了!

  • http://en.cppreference.com/w/cpp/header/algorithm
  • http://www.cplusplus.com/reference/functional/bind1st/
  • https://stackoverflow.com/questions/356950/c-functors-and-their-uses
  • http://en.cppreference.com/w/cpp/language/lambda

另外,我们的oj已经支持C++17了

FineArtz's solution

/* STL-algorithm */
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, m, tmp;
    scanf("%d%d", &n, &m);
    vector<int> v;
    //cin >> n >> m;
    for (int i = 0; i < n; ++i){
        scanf("%d", &tmp);
        //cin >> tmp;
        v.push_back(tmp);
    }
    while (m--){
        int t, i, j, a, b, c;
        int ans;
        vector<int>::iterator ite = v.begin();
        scanf("%d%d%d", &t, &i, &j);
        switch(t){
            case 1:
                sort(v.begin() + i, v.begin() + j);
                break;
            case 2:
                reverse(v.begin() + i, v.begin() + j);
                break;
            case 3:
                for (auto it = v.begin() + i; it != v.begin() + j; ++it)
                    printf("%d ", *it);
                    //cout << *it << ' ';
                printf("\n");
                //cout << endl;
                break;
            case 4:
                ans = *min_element(v.begin() + i, v.begin() + j);
                printf("%d\n", ans);
                //cout << *minn << endl;
                break;
            case 5:
                scanf("%d", &a);
                //cin >> a;
                ans = count_if(v.begin() + i, v.begin() + j, [a](int x){return x > a;});
                printf("%d\n", ans);
                //cout << ans << endl;
                break;
            case 6:
                scanf("%d", &a);
                ite = find(v.begin() + i, v.begin() + j, a);
                ans = distance(v.begin(), ite);
                printf("%d\n", ans);
                //cout << ans << endl;
                break;
            case 7:
                scanf("%d%d", &a, &b);
                //cin >> a >> b;
                replace(v.begin() + i, v.begin() + j, a, b);
                break;
            case 8:
                scanf("%d%d%d", &a, &b, &c);
                stable_partition(v.begin() + i, v.begin() + j, [a, b, c](int x){return a * x * x + b * x + c > 0;});
                break;
            default:
                break;
        }
    }
    return 0;
}