非正经题解
2025-08-04 20:51:40
发布于:浙江
25阅读
0回复
0点赞
这题数据较弱,暴力优化后可AK.
(Tips:老师已经知道了可能要优化数据力)
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node
{
	int v,n;
} a[500005];
bool cmp(node x,node y)
{
	return x.v < y.v;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i].v;
		a[i].n = i;
	}
	sort(a+1,a+n+1,cmp);
	for(int i = 1;i <= m;i++)
	{
		int l,r;
		cin >> l >> r;
		for(int j = 1;j <= n;j++)
			if(a[j].n >= l && a[j].n <= r)
			{
				cout << a[j].v << " ";
				break;
			}
	}
	return 0;
}
未优化前代码:20pts
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[500005];
int main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	for(int i = 1;i <= m;i++)
	{
		int l,r;
		cin >> l >> r;
		sort(a+l,a+r);
		cout << a[l] << " ";
	}
	return 0;
}
纯暴力时,由于sort()平均复杂度为,因此本方法时间复杂度为.对于,有,会超时。
优化后时间复杂度将为,并有剪枝(? 虽然剪枝一般说的是搜索,但是找不到好的形容词了)优化,且本题数据较弱,故能AK.
全部评论 1
- ?申金 知道原理是啥吗就抄 - 2025-08-08 来自 浙江 0- ?怎么了 - 2025-08-09 来自 浙江 0
 










有帮助,赞一个