45pts,求复杂度分析
查看原帖
45pts,求复杂度分析
327813
__lyh__楼主2021/7/15 22:58
#include<bits/stdc++.h>
#define maxn 8000005
#define ll long long
using namespace std;
inline ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
vector<ll> e;
ll n,m,q,u,v,t;
ll ans[maxn];
int cnt;
int main()
{
	n=read();m=read();q=read();u=read();v=read();t=read();
	for(int i=1;i<=n;i++)
	{
		e.push_back(read());
	}
	sort(e.begin(),e.end());
	int cnt=n;
	for(int i=1;i<=m;i++)
	{
		int num_max=*(e.end()-1);
		num_max+=(i-1)*q;
		ans[i]=num_max;
		int a1=num_max*u/v;
		int a2=num_max-a1;
		a1-=i*q;
		a2-=i*q;
		e.pop_back();
		e.insert(lower_bound(e.begin(),e.end(),a1),a1);
		e.insert(lower_bound(e.begin(),e.end(),a2),a2);
		cnt++;
	}
	for(int i=t;i<=m;i+=t)
	{
		printf("%d ",ans[i]);
	}
	printf("\n");
	for(int i=t;i<=cnt;i+=t)
	{
		printf("%d ",e[cnt-i]+q*m);
	}
}

看似复杂度O(nlogn)O(nlogn),为何45pts(其他全T)?

2021/7/15 22:58
加载中...