写了个暴力,AC+RE+T+WA,求

P1631 序列合并

@[ytyuhuan](/user/225797) 您的代码 时间复杂度为 $O(n^3)$,此处 $n\le10^5$,肯定会 T。 应该需要 $O(nlogn)$ 的算法,比如堆、优先队列才能过。
by linch @ 2024-02-19 19:22:21


@[ytyuhuan](/user/225797) 另外,RE 的原因应该是 $a$ 和 $b$ 数组越界,您只开了 $10^4$。
by linch @ 2024-02-19 19:23:55


@[ytyuhuan](/user/225797) ``` #include<bits/stdc++.h> #define int long long using namespace std; int a[100005],b[100005]; int d[100000005]; signed main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); for(int j=1;j<=n;j++) cin>>b[j]; sort(b+1,b+n+1); int ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n/i;j++) { int x=a[i]+b[j]; d[++ans]=x; } } sort(d+1,d+ans+1); for(int i=1;i<=n;i++) cout<<d[i]<<" "; return 0; } ```
by ChenJiaMing110122 @ 2024-02-20 10:16:16


@[ytyuhuan](/user/225797) 有没有种可能,你的暴力打错了,我的代码已附上。
by ChenJiaMing110122 @ 2024-02-20 10:17:13


|