題目鏈接
可以很容易地想出暴力思路，但復雜度高達O(n2)，所以必須優化
思路1：不難發現在a陣列到i，b陣列到j處，在它們前面的有i*j個，這i*j個數不可能比它大，所以只要在暴力列舉程序中判斷i*j<=n即可，
最后只要對和排序，求出前n個，注意存放和的陣列不能只有n個，
vector<int> sum;
for(int i=1; i<=n; i++) { for(int j=1; i*j<=n; j++) { sum.push_back(a[i]+b[j]); } } sort(sum.begin(),sum.end()); printf("%u",sum[0]); for(int i=1; i<n; i++) { printf(" %u",sum[i]); }
思路2：
暴力列舉的解法里，除了全部n2個弄完再排序之外，還可以使用一個優先佇列，
由于要求最小的n個，所以這個佇列的“容積”是n，一旦元素個數已達到n個，并且新的和小于隊頭，那么就先出隊再將新的和入隊，
注意到：當a到i，b到j時，如果新的和大于隊頭，那么后面再怎么遍歷也不會小于隊頭了，所以可以這樣優化：
for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(q.size()<n) { q.push(a[i]+b[j]); } else { if(a[i]+b[j]>q.top()) break; q.pop(); q.push(a[i]+b[j]); } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/468012.html
標籤：其他