VIRTUALS

the virtual labs for the virtuals

0%

C++算法题输入输出小技巧总结

Posted on Edited on In , ,

摘要：
OJ输入输出小技巧总结。

输入一行没有空格的字符串

1
2
std::string s;
cin >> s;

输入一行带有空格的字符串

1
2
std::string s;
std::getline(cin, s);

循环输入直到无数据源

1
2
3
4
5
int a;
for (; cin >> a; )
{
    // do something
}

stringstream 流式输入

很方便地进行字符串分割和字符串到其他类型的转换。

  • 输入：
    1 2 3 4 5 6 7 8 9
    34 56 85 19 0 88
    995 668
    10086
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N = 1010;
int ar[N];

int main()
{
    string s;
    stringstream ss;

    for (; getline(cin, s);) {
        ss << s;    // 将s放入ss中
        for (int i = 0, t = 0; ss >> t; i++) {
            ar[i] = t; 
        }
    }
}

提高输入输出效率

1
2
3
4
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// start cin or cout

对于大量数据输入，少量输出的情况，可以这样写：

1
cin.tie(nullptr)->sync_with_stdio(false);

Class模式的OJ（如LeetCode）提高输入输出

很简单，直接在class外写上如下函数：

1
2
3
4
5
6
static const auto io_sync_off=[](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return nullptr;
}();

举例：

原题链接： 牛客剑指Offer JZ35. 数组中的逆序对

使用前：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int tmp[1000010];
    long long cnt = 0;
    //int _mod = 1000000007;
    int InversePairs(vector<int> data) {
        int n = data.size();
        helper(0, n - 1, data);
        return cnt % 1000000007;
    }
     
    void helper(int lo, int hi, vector<int>& data) {
        if (lo >= hi) return;
         
        int mid = lo + hi >> 1;
        helper(lo, mid, data), helper(mid + 1, hi, data);
         
        // backtrack       
        int i = lo, j = mid + 1;
        int idx = 0;
        // merge sort and compare
        for (; i <= mid && j <= hi; idx++) {
            if (data[i] <= data[j]) tmp[idx] = data[i++];
            else {
                tmp[idx] = data[j++];
                cnt += mid - i + 1;
            }
        }
        for (; i <= mid;) tmp[idx++] = data[i++];
        for (; j <= hi;) tmp[idx++] = data[j++];
        // override
        for (idx = 0, i = lo; i <= hi;) data[i++] = tmp[idx++];
    }
};

运行时间： 113 ms

使用后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
static const auto io_sync_off=[](){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int tmp[1000010];
    long long cnt = 0;
    //int _mod = 1000000007;
    int InversePairs(vector<int> data) {
        int n = data.size();
        helper(0, n - 1, data);
        return cnt % 1000000007;
    }
     
    void helper(int lo, int hi, vector<int>& data) {
        if (lo >= hi) return;
         
        int mid = lo + hi >> 1;
        helper(lo, mid, data), helper(mid + 1, hi, data);
         
        // backtrack       
        int i = lo, j = mid + 1;
        int idx = 0;
        // merge sort and compare
        for (; i <= mid && j <= hi; idx++) {
            if (data[i] <= data[j]) tmp[idx] = data[i++];
            else {
                tmp[idx] = data[j++];
                cnt += mid - i + 1;
            }
        }
        for (; i <= mid;) tmp[idx++] = data[i++];
        for (; j <= hi;) tmp[idx++] = data[j++];
        // override
        for (idx = 0, i = lo; i <= hi;) data[i++] = tmp[idx++];
    }
};

运行时间： 79 ms

舒服了。