社区讨论

求解答：关于strcmp时间复杂度

cchenhaoyang2008
P9868[NOIP2023] 词典参与者 2已保存回复 8

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@m29zmmuy
此快照首次捕获于
2024/10/15 13:13
去年
此快照最后确认于
2025/11/04 17:09
4 个月前
查看原帖

如题，关于strcmp时间复杂度

以下代码在测试点10会被卡（90分）（手写了一个asmaller，相当于strcmp）

CPP
#include<bits/stdc++.h>
using namespace std;
char s[3001][3001];
char shs[3001][3001];
char sls[3001][3001];

bool asmaller(string a,string b,int len){
	for(int i=0;i<len;i++){
		if(a[i]==b[i]) continue;
		else if(a[i]<b[i]) return true;
		else return false;
	}
	return false;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		strcpy(sls[i],s[i]);
		sort(sls[i],sls[i]+m,greater<char>());
		strcpy(shs[i],sls[i]);
		reverse(shs[i], shs[i]+m);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(asmaller(shs[i],sls[j],m) &&i!=j){
				cout<<0;
				break;
			}
			if(j==n){
				cout<<1;
				break;
			}
		}
	}
}

用strcmp就不会

CPP
#include<bits/stdc++.h>
using namespace std;
char s[3001][3001];
char shs[3001][3001];
char sls[3001][3001];


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		strcpy(sls[i],s[i]);
		sort(sls[i],sls[i]+m,greater<char>());
		strcpy(shs[i],sls[i]);
		reverse(shs[i], shs[i]+m);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(strcmp(shs[i],sls[j])>0 &&i!=j){
				cout<<0;
				break;
			}
			if(j==n){
				cout<<1;
				break;
			}
		}
	}
}
asmaller和strcmp的复杂度不都是O(n)吗？ 为什么第一个会被卡？(而且相差很远，第一个4000ms，第二个150ms)。求解答。

回复

共 8 条回复，欢迎继续交流。

正在加载回复...