C++ vector与cout运行内存与时间问题

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 32M，其他语言64M

P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内）

如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。

输入描述:
第一行输入点集的个数 N， 接下来 N 行，每行两个数字代表点的 X 轴和 Y 轴。
对于 50%的数据, 1 <= N <= 10000;
对于 100%的数据, 1 <= N <= 500000;

输出描述:
输出“最大的” 点集合， 按照 X 轴从小到大的方式输出，每行两个数字分别代表点的 X 轴和 Y轴。

输入例子1:
5
1 2
5 3
4 6
7 5
9 0

输出例子1:
4 6
7 5
9 0

No.1

#include
#include
#include
using namespace std;
int main(int argc, char** argv){
    int n;
    cin>>n;
    vector<vector<int> > a(n, vector<int>(2));
    for(int i = 0; i < n; i++){
        cin>>a[i][0]>>a[i][1];
    }
    sort(a.begin(), a.end());
    int max = a[n-1][1];
    int b[n][2];
    b[0][0] = a[n-1][0];
    b[0][1] = a[n-1][1];
    int q = 1;
    for(int i = n-2; i >= 0; i--){
        if(a[i][1] > max){
            b[q][0] = a[i][0];
            b[q][1] = a[i][1];
            q++;
            max = a[i][1];
        }
    }
    for(int i = q-1; i >= 0; i--){
        if(i== (-1)){
            break;
        }
        cout<<b[i][0]<<" "<<b[i][1]<<endl;
    }
    return 0;
}
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

400000用例的时候超时

No.2

#include
#include
#include
using namespace std;
int main(int argc, char** argv){
    int n;
    cin>>n;
    vector<vector<int> > a(n, vector<int>(2));
    for(int i = 0; i < n; i++){
        cin>>a[i][0]>>a[i][1];
    }
    sort(a.begin(), a.end());
    int max = a[n-1][1];
    int b[n][2];
    b[0][0] = a[n-1][0];
    b[0][1] = a[n-1][1];
    int q = 1;
    for(int i = n-2; i >= 0; i--){
        if(a[i][1] > max){
            b[q][0] = a[i][0];
            b[q][1] = a[i][1];
            q++;
            max = a[i][1];
        }
    }
    for(int i = q-1; i >= 0; i--){
        if(i== (-1)){
            break;
        }
        printf("%d %d\n",b[i][0],b[i][1]);
    }
    return 0;
}
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

No.3

将vector a 利用 struct node 代替

#include
#include
#include
#include
using namespace std;
typedef struct node{
    int x;
    int y;
    node(int _x,int _y){x=_x,y=_y;}
}Node;

bool cmp(node a, node b){
    if(a.x != b.x) return a.x > b.x;
    else return  a.y > b.y;
}

int main(int argc, char** argv){
    int n;
    cin>>n;
    vector<Node>aa;
    Node a(0,0);
    for(int i = 0; i < n; i++){
        cin>>a.x>>a.y;
        aa.push_back(a);
    }
    sort(aa.begin(), aa.end(),cmp);
    int max = aa[0].y;
    stack<int> q;
    q.push(0);
    for(int i = 1; i < n; i++){
        if(aa[i].y > max){
            max = aa[i].y;
            q.push(i);
        }
    }
    int nn = 0;
    while(!q.empty()){
        nn = q.top();
        q.pop();
        printf("%d %d\n",aa[nn].x,aa[nn].y);
    }
    return 0;
}
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
42
43

总结

在遇到 坐标结构的数据，尽量不要用嵌套的vector数据结构，用struct node代替，在输出时printf更快一点。

今早室友说

于是

原因：endl会新建行并清除缓存区，而“\n”只换行