前言

有一個東西卡了我一會

折疊N*或N+
正整數集 (由全體正整數組成的集合) N*:={1,2,3,…,n,…}

---

題目

洛谷P2085
OJ1370
給出n個ai,bi,ci。定義一個函數

fi(x)=aix2+bix+ci(x∈N?)fi(x)=aix2+bix+ci(x∈N?)
然后求最小的m個數

---

解題思路

這道題比較簡單，一下就想到了。最重要的是得知道：

fi(1)<fi(2)<fi(3)<...<fi(n)<...fi(1)<fi(2)<fi(3)<...<fi(n)<...
然后就開始時都是x=1的，開一個小根堆，然后取最小的輸出并且將那個f的x累加。然后維護

---

代碼

#include<cstdio> #include<algorithm> using namespace std; struct woc{int ans,ai,bi,ci,xi;//結構體 }; woc a[10001]; int n,m,num; void up(int x)//維護堆 {while (x>1 && a[x/2].ans>a[x].ans){swap(a[x/2],a[x]);x/=2;} } void down(int x)//維護堆 {int y;while (x*2<=num && a[x*2].ans<a[x].ans || x*2+1<=num && a[x*2+1].ans<a[x].ans){y=x*2;if (y+1<=num && a[y].ans>a[y+1].ans) y++;swap(a[y],a[x]);x=y;} } int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){num++;scanf("%d%d%d",&a[num].ai,&a[num].bi,&a[num].ci);a[num].xi=1;a[num].ans=a[num].ai*a[num].xi*a[num].xi+a[num].bi*a[num].xi+a[num].ci;//求值up(num);//建堆}輸入while (m>0){printf("%d ",a[1].ans);//輸出a[1].xi++;//累加xa[1].ans=a[1].ai*a[1].xi*a[1].xi+a[1].bi*a[1].xi+a[1].ci;//重新求值down(1);//維護堆m--;//減少} }

總結

以上是生活随笔為你收集整理的洛谷P2085ssl1411OJ1370-最小函数值【堆,贪心】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。