如果用暴力解法，这题顶多是个橙
by cyh_qwq @ 2023-06-22 14:39:16
@[cyh_qwq](/user/550107)
## 我家暴力怎么你了？
### 时间复杂度
计算了一下正常枚举差不多在`4e8`，洛谷机子1秒可以跑`1e9`，你说的暴力应该是`n*m*log(m)=4*1e9`，这个过不了，但我这个可以过。
### 空间复杂度
看似使用小根堆，可以使用大根堆保持m个最小的，然后倒着输出，这样只存了m个数。
### 正确性
首先第二个循环从1到100是对的， `1≤Ai≤10,Bi≤100,Ci≤10e4`
a,b,c最小时，他肯定弄的答案多，
所以设`a=1,b=1,c=1`，为了防止其他值比他小，所以设极端值`a=10,b=100,c=10000`。
`Aix*X+Bix+Ci`
当`x=10000，a=1,b=1,c=1`时,结果是`1e8+1e4+1`
当x=9000时，`a=10,b=100,c=10000`时，结果是`8.1*1e7+9e5+1e4<1e8+1e4`
所以直接枚举1e3肯定对，因为无论a、b、c是多少，x=1e3肯定取不到了，直接枚举，正确性可以保证。
by a1a2a3a4a5 @ 2023-07-08 14:07:05
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a,b,c,sz[11000];
priority_queue<long long> dui;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a>>b>>c;
for(int j=1;j<=1000;j++)
{
dui.push(a*j*j+b*j+c);
if(dui.size()>m) dui.pop();
}
}
for(int i=m;i>=1;i--) sz[i]=dui.top(),dui.pop();
for(int i=1;i<=m;i++) cout<<sz[i]<<" ";
return 0;
}
```
by a1a2a3a4a5 @ 2023-07-08 14:08:58
@[a1a2a3a4a5](https://www.luogu.com.cn/user/658008)
我指的暴力是O(m^2n)的算法，这个算法也确实能A。你这个算法确实快了点，但正常比赛的评测机可能也跑不了这么快。我是用的O(mlog(n))算法。
by cyh_qwq @ 2023-07-09 14:54:33
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N=3e4+5;
int n,tot,m;
int a[N],b[N],c[N];
int s[N];
long long heap[N];
int idx[N];
inline void up(int p){
while(p>1){
if(heap[p]<heap[p/2]){
swap(heap[p],heap[p/2]);
swap(idx[p],idx[p/2]);
p/=2;
}
else break;
}
}
inline void down(int p){
int s=p*2;
while(s<=tot){
if(s<tot&&heap[s]>heap[s+1])s++;
if(heap[s]<heap[p]){
swap(heap[s],heap[p]);
swap(idx[s],idx[p]);
p=s,s=p*2;
}
else break;
}
}
inline void insert(long long x,int id){
heap[++tot]=x;
idx[tot]=id;
up(tot);
}
inline void del(){
heap[1]=heap[tot--];
idx[1]=idx[tot+1];
down(1);
}
int main(){
scanf("%d%d",&n,&m);
int k;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a[i],&b[i],&c[i]);
s[i]=1,insert(s[i]*s[i]*a[i]+s[i]*b[i]+c[i],i);
}
int id;
for(int i=1;i<=m;i++){
printf("%lld ",heap[1]);
id=idx[1];
del();
s[id]++;
insert(s[id]*s[id]*a[id]+s[id]*b[id]+c[id],id);
}
}
```
by cyh_qwq @ 2023-07-09 14:55:28
RT,如果你觉得这个题不用这么做，那我也无话可说
by cyh_qwq @ 2023-07-09 14:56:45
这暴力不吸氧20，吸氧100啊
by chen_z @ 2023-07-19 19:20:11
确实，我这种离谱程序都能过\
[每次循环重新建堆吸氧6.24s](https://www.luogu.com.cn/record/145724938)
by qwezky @ 2024-02-02 11:05:39
这个也过了！！
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000001],s;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int A,B,C;
cin>>A>>B>>C;
for(int j=1;j<=100;j++){
a[++s]=A*j*j+B*j+C;
}
}
sort(a+1,a+s+1);
for(int i=1;i<=m;i++){
cout<<a[i]<<" ";
}
return 0;
}
```
[记录](https://www.luogu.com.cn/record/145724938)
by shicj @ 2024-02-11 19:05:44
氧气好闪，拜谢氧气
by 菜のcrzOvO @ 2024-02-17 09:07:20