正题

题目链接:http://noi.ac/contest/266/problem/793

---

题目大意

给定$m$个函数$f_z(x)={\sum }_{i=0}^k{a}_{z,i}\ast x^i$，然后求这些函数的并集中第$n$大的数。

---

解题思路

我们显然可以得出$f_z(i)<f_z(i+1)$

所以我们可以先用对存下所以的$f_z(1)$，然后每次取出一个将其$x$增大再丢回去，第$n$次就是答案。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define ll long long using namespace std; struct node{ll num,w,t; }; bool operator<(const node &x,const node &y) {return x.w>y.w;} const ll N=3e4+10; ll n,m,k,a[N][10]; priority_queue<node> q; int main() {scanf("%lld%lld%lld",&n,&m,&k);for(ll i=1;i<=m;i++){ll w=0;for(ll j=0;j<=k;j++){scanf("%lld",&a[i][j]);w+=a[i][j];}q.push((node){i,w,1});}while(--n){node c=q.top();q.pop();ll w=0,z=1;for(ll i=0;i<=k;i++){w+=a[c.num][i]*z;z*=c.t+1;}q.push((node){c.num,w,c.t+1});}printf("%lld",q.top().w); }

总结

以上是生活随笔为你收集整理的NOI.AC-序列【堆】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。