目錄

1.P2085 最小函數值?

題目

分析

方法1:暴力求解

方法2:二次函數的性質(推薦!)

代碼

提交結果

2.P1631 序列合并

分析

方法1:建兩個堆

第一版代碼

提交結果

第二版代碼

提交結果

第三版代碼

提交結果

方法2:只建一個堆

代碼

提交結果

---

1.P2085 最小函數值?

題目

https://www.luogu.com.cn/problem/P2085

分析

從題目的"輸出將這 n 個函數所有可以生成的函數值排序后的前 m 個元素"可以看出是堆排序的TopK問題

方法1:暴力求解

求出所有函數中的m個值,然后取前m個,n個函數各有m個值,時間復雜度過高,為,不建議使用

方法2:二次函數的性質(推薦!)

以測試用例分析畫表:

會發現:x==4及之后x的值,均是最小,只有它的函數值需要入隊

原因:的最高次的系數為1,階位最高比和都要小,同是二次函數,二次項前的系數決定階位的高低,因此有:

從圖像上也可以看出:

算法:首先將x==1的所有函數值計算出來,然后入堆,然后每次拿出最小的那個函數值來打印,把對應的之后刪除堆頂元素,把對應的下一個函數值f(x+1)入堆

因為每次拿出最小的那個函數值,所以建立小根堆

因為要將對應的下一個函數值入堆,所以需要知道是哪個函數算的,因此要記錄函數的編號,要算f(x+1),需要知道x,因此入堆的元素是結構體,建小根堆需要運算符重載

struct node
{ull f_x;//f(x)函數值 ull num;//函數的編號 ull x;bool operator<(const node& _node) const{return f_x>_node.f_x;//建立小根堆 }		
};

?例如

設f(x)=4x^2+5x+3,編號為1;g(x)=3x^2+4x+5,編號為2;h(x)=x^2+7x+1,編號為3;先將{12,1,1}、{12,2,1}、{9,3,1}入堆,發現函數值9最小,因此刪除堆頂元素后將{h(1+1),3,2}入堆,以此類推......

注意:刪除堆頂元素只能進行m次

代碼

#include <iostream>
#include <queue>
#define endl "\n"  
using namespace std;
typedef unsigned long long ull;
const int N=1e5+10;
struct node
{ull f_x;//f(x)函數值 ull num;//函數的編號 ull x;bool operator<(const node& _node) const{return f_x>_node.f_x;//建立小根堆 }		
};
priority_queue<node> q;
ull A[N],B[N],C[N]; 
int main()
{ios::sync_with_stdio(false);cin.tie(0);ull n,m;cin>>n>>m;for (ull i=1;i<=n;i++)cin>>A[i]>>B[i]>>C[i];for (ull j=1;j<=n;j++)q.push({A[j]+B[j]+C[j],j,1});//x=1的所有函數值入隊while(m--) {node tmp=q.top();cout<<q.top().f_x<<" ";q.pop();q.push({A[tmp.num]*(tmp.x+1)*(tmp.x+1)+B[tmp.num]*(tmp.x+1)+C[tmp.num],tmp.num,tmp.x+1});} return 0;
}

提交結果

2.P1631 序列合并

fhttps://www.luogu.com.cn/problem/P1631

分析

線索"從小到大表示這 N 個最小的和",顯然屬于TopK問題

方法1:建兩個堆

由于是從小到大,應該建大根堆,將a[i]+b[j]的結果存入其中,保持大根堆內含N個元素,如果直接打印其堆頂元素的話結果是從大到小的,可以再建一個小根堆,將大根堆的堆頂元素存入小根堆,最后再打印大根堆的堆頂元素

第一版代碼

#include <iostream>
#include <queue>
using namespace std;
const int N1=1e6+10;
const int N2=1e3+10;
typedef unsigned long long ull;
ull n,a[N1],b[N1],c[N2],d[N1],s;
priority_queue<ull,vector<ull>,less<ull>> tmp_heap;
priority_queue<ull,vector<ull>,greater<ull>> result_heap;
int main()
{cin>>n;for (int i=0;i<n;i++){cin>>a[i];}for (int i=0;i<n;i++){cin>>b[i];}for (int i=0;i<n;i++){for (int j=0;j<n;j++){c[s]=a[i]+b[j];if (tmp_heap.size()<n)		{tmp_heap.push(c[s]);	} else if (tmp_heap.top()>c[s]){tmp_heap.pop();tmp_heap.push(c[s]);}s++;}}	while (tmp_heap.size()){result_heap.push(tmp_heap.top());tmp_heap.pop();		} while(result_heap.size()){cout<<result_heap.top()<<" ";result_heap.pop();}return 0;
}

提交結果

超出內存的限制,其實不用創建c[N]數組,直接使用臨時變量存儲a[i]+b[j]的結果,節約空間

第二版代碼

#include <iostream>
#include <queue>
using namespace std;
const int N1=1e6+10;
const int N2=1e3+10;
typedef unsigned long long ull;
ull n,a[N1],b[N1],d[N1],c;
priority_queue<ull,vector<ull>,less<ull>> tmp_heap;
priority_queue<ull,vector<ull>,greater<ull>> result_heap;
int main()
{cin>>n;for (int i=0;i<n;i++){cin>>a[i];}for (int i=0;i<n;i++){cin>>b[i];}for (int i=0;i<n;i++){for (int j=0;j<n;j++){c=a[i]+b[j];if (tmp_heap.size()<n)		{tmp_heap.push(c);	} else if (tmp_heap.top()>c){tmp_heap.pop();tmp_heap.push(c);}}}	while (tmp_heap.size()){result_heap.push(tmp_heap.top());tmp_heap.pop();		} while(result_heap.size()){cout<<result_heap.top()<<" ";result_heap.pop();}return 0;
}

提交結果

解決方法:有超時,說明for循環的次數過多,注意到題目的"單調不降序列",應盡量減少循環次數,觀察發現,設外循環為變量i,內循環為變量j,當i不變時,隨著j的增大a[i]+b[j]的值也在增大或者不變,當a[i]+b[j]在增大時,必定存在某個狀態有tmp_heap.top()<c,不用入堆,應該立刻退出內循環,減少循環次數?

第三版代碼

#include <iostream>
#include <queue>
using namespace std;
const int N1=1e6+10;
const int N2=1e3+10;
typedef unsigned long long ull;
ull n,a[N1],b[N1],d[N1],c;
priority_queue<ull,vector<ull>,less<ull>> tmp_heap;
priority_queue<ull,vector<ull>,greater<ull>> result_heap;
int main()
{cin>>n;for (int i=0;i<n;i++){cin>>a[i];}for (int i=0;i<n;i++){cin>>b[i];}for (int i=0;i<n;i++){for (int j=0;j<n;j++){c=a[i]+b[j];if (tmp_heap.size()<n)		{tmp_heap.push(c);	} else if (tmp_heap.top()>c){tmp_heap.pop();tmp_heap.push(c);}if (tmp_heap.top()<c)break;		}}	while (tmp_heap.size()){result_heap.push(tmp_heap.top());tmp_heap.pop();		} while(result_heap.size()){cout<<result_heap.top()<<" ";result_heap.pop();}return 0;
}

提交結果

方法2:只建一個堆

只建小根堆,由題目的"單調不降序列"

先將a[i]+b[0]入堆(堆中元素正好N個),之后每次先出堆頂元素,再入剩下的元素(a[i]+b[1]、a[i]+b[2]、...、a[i]+b[n]),這樣每次出堆的元素都是當前堆中最小的,執行N次出堆即可,時間復雜度為

以題目的測試用例為例

2+1=3 6+1=7 6+1=7

2+4=6 6+4=10 6+4=10

2+8=10 6+8=14 6+8=14

一行一行看,會發現:

a[1] + b[1] ≤ a[1] + b[2] ≤ a[1] + b[3] ≤ ... ≤ a[1] + b[n]
a[2] + b[1] ≤ a[2] + b[2] ≤ a[2] + b[3] ≤ ... ≤ a[2] + b[n]
a[3] + b[1] ≤ a[3] + b[2] ≤ a[3] + b[3] ≤ ... ≤ a[3] + b[n]
......

先將a[i]+b[1]入堆(因為是每一行不等式中最小的那個),之后取堆頂元素后再入堆,執行N次

能只將和入堆嗎?如果不用兩重循環的話

答:不能,只將和入堆會找不到下一個入堆的元素,入堆的應該是結構體

代碼

#include <iostream>
#include <queue>
using namespace std;
const int N1=1e6+10;
int n,a[N1],b[N1];
struct node
{int i;int j;int sum;bool operator<(const node& x)const{return sum>x.sum;	}	
};priority_queue<node> heap; 
int main() 
{cin>>n;for (int i=0;i<n;i++)cin>>a[i];for (int i=0;i<n;i++)cin>>b[i];//前n個入堆for (int i=0;i<n;i++){heap.push({i,0,a[i]+b[0]}); }	//剩下的入堆for (int k=0;k<n;k++){node tmp=heap.top();heap.pop();		cout<<tmp.sum<<" ";if (tmp.j+1<n) {heap.push({tmp.i,tmp.j+1,a[tmp.i]+b[tmp.j+1]}); }} return 0;
}

提交結果