站外题求助!!!
查看原帖
站外题求助!!!
1040559
_wangleting123_楼主2023/10/2 20:12

问题描述: 佛山创文要求大家要遵守交通规则,发扬尊老爱幼精神。

乐乐想做一个关于公交文化的调查。他专门为排队上车发明了一套叫做“愧疚指数”的分析系统,就是在队列中把人分为三等:第一等为优先级最高,最需要照顾的老人、小孩、孕妇等,应该最先上车,编号为1;第二等是女人,为了发扬绅士风度,男人是要让女人先上车的,但优先级小于一等,编号为2;第三等是男人,优先级最低,应该排在最后面,编号为3。

所谓的“愧疚指数”是指队列中一个人后面有多少人的优先级比他高,如队列中有5个人分别为:3 2 1 2 1,那么这5个人的“愧疚指数”分别为:4 2 0 1 0。

现在已经知道一个队列,请你帮乐乐算出队列中每个人的“愧疚指数”。

输入格式: 第一行是一个正整数n,表示一共有多少个人排队。

第二行有n个用空格隔开的正整数,它们从左至右给出了队列中的n个人的编号。

输出格式: 输出一行:有n个用空格分开的正整数,代表队列中每个人的“愧疚指数”。

输入样例: 5 3 2 1 2 1 输出样例: 4 2 0 1 0

数据规模: 对于80%的数据,n≤10000;

对于100%的数据,n≤200000。

#include<iostream>
using namespace std;
int n,a[100001],b[100001];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(a[i]>a[j])b[i]++;
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<b[i]<<' ';
	}
	return 0;
}

出现了->80 Time Exceeded<-这种问题 那怎么优化时间复杂度?

2023/10/2 20:12
加载中...