# 关于优先队列没跑过sort ??时间复杂度

@独赏烟花笑 2021-05-04 21:30 回复

#include <iostream>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define max 1000005
int n;
long long k[max];
long long mvl,nmvl;
struct Node{
long long value;
int index;
}node[max];
bool cmp(Node a,Node &b){
return a.value<b.value;
}
int main(int argc, char** argv) {
cin>>n;
for(int i=1;i<=n;i++)cin>>k[i];
mvl=k[1];
for(int i=2;i<=n;i++){
if(k[i]*i>mvl)
mvl=k[i]*i;
}
for(int i=1;i<=n;i++){
node[i].index=i;
node[i].value=k[i];
}
sort(node+1,node+n+1,cmp);
int maxpos=node[n].index;
nmvl=0;
for(int i=n-1;i>=1;i--){
long long val=node[i].value;
int ind=node[i].index;
if(val*(maxpos+ind)>nmvl)
nmvl=val*(maxpos+ind);
if(ind>maxpos)maxpos=ind;
}
if(mvl>nmvl)
cout<<mvl;
else cout<<nmvl;
return 0;
}

#include <iostream>
#include <queue>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define max 1000005
int n;
long long k[max];
long long mvl,nmvl;
struct node{
long long value;
int index;
bool operator<(const node &n)const{
return value<n.value;
}
};
priority_queue<node>q;
int main(int argc, char** argv) {
cin>>n;
for(int i=1;i<=n;i++)cin>>k[i];
mvl=k[1];
for(int i=2;i<=n;i++){
if(k[i]*i>mvl)
mvl=k[i]*i;
}
for(int i=1;i<=n;i++){
q.push((node){k[i],i});
}
int maxpos=q.top().index;
q.pop();
nmvl=0;
while(!q.empty()){
long long val=q.top().value;
int ind=q.top().index;
if(val*(maxpos+ind)>nmvl)
nmvl=val*(maxpos+ind);
if(ind>maxpos)maxpos=ind;
q.pop();
}
if(mvl>nmvl)
cout<<mvl;
else cout<<nmvl;
return 0;
}
@_Anchor  2021-05-04 22:01 回复 举报

@Tsukimaru 2021-05-05 07:53 回复 举报

@独赏烟花笑 举个例子：

for(int i=1; i<=n; i++)
for(int j=1; j<=10; j++)
sum += i + j;

for(int i=1; i<=n; i++)
sum += 10 * i + 55;