2016 UESTC Training for Data Structures D – 卿学姐与魔法 优先队列、构造

My Solution

用STL里的优先队列直接维护前n+1小的数字

ptr = 0

先 i = ptr 然后A + B1 + B2 + …… B(n-1)

然后 j = 1 B1 + A2 + ……A(n-1)

这样依次下去，

当 Aptr + B(ptr+1) 已经比.top()大了，则可以break了。

故最好的情况O(n), 最差的情况(┬＿┬)不会算但绝对小于O(n^2)

竟然用了do while 开心

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 100000+8;

int A[maxn], B[maxn];
priority_queue pq;
vector vec;
//2*sort This has been test in A + B problem
int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &A[i]);
    sort(A, A+n);

    for(int i = 0; i < n; i++)
        scanf("%d", &B[i]);
    sort(B, B+n);

    int cnt = 0;     // 0 or 1 just see the test ☺
    int ptr = 0;
    do{
        for(int j = ptr; j < n ; j++){ if(cnt != n+1){cnt++; pq.push(A[ptr]+B[j]);} else{ if(pq.top() > A[ptr]+B[j]){
                    pq.push(A[ptr]+B[j]);
                    pq.pop();
                }
                else break;
            }
        }

        for(int j = ptr+1; j < n ; j++){ if(cnt != n+1){cnt++; pq.push(A[j]+B[ptr]);} else{ if(pq.top() > A[j]+B[ptr]){
                    pq.push(A[j]+B[ptr]);
                    pq.pop();
                }
                else break;
            }
        }
        ptr++;
    } while(pq.top() >= A[ptr]+B[ptr] && ptr < n); pq.pop(); while(!pq.empty()){ vec.push_back(pq.top()); pq.pop(); } for(int i = n-1; i >= 0; i--)
        printf("%dn", vec[i]);
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx