思路错了?
  • 板块学术版
  • 楼主Lordi
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/18 20:11
  • 上次更新2024/8/18 22:44:05
查看原帖
思路错了?
1400000
Lordi楼主2024/8/18 20:11
秩序(order)

小新是一个见习的魔法师,他需要完成一些任务。
在一个充满魔法和数字的王国中,有一个古老的传说,传说中有一个由神秘数字组成的数列,这些数字被赋予了魔法力量。数列中的每个数字都在 1 到 k 之间,它们按照特定的顺序排列,维持着王国的和谐与秩序。然而,一个邪恶的巫师施法打乱了数列,导致王国的力量失衡。
为了恢复秩序,必须创造出一个新的数列,这个新数列的数字同样要在 1 到 k 之间,但有一个关键的条件:新数列不能成为原数列的子序列。子序列是指从原数列中选取部分数字(不必连续)所形成的序列。
小新决定解决这个难题。他们需要找到这样一个新数列,它的每个数字都不违反 1 到 k 的限制,同时确保新数列不是原数列的子序列。此外,他们还需要保证新数列的长度尽可能短,以最小化魔法能量的消耗。
【输入格式】
第一行:两个整数表示n和k;
第二行:n个整数表示该序列。
【输出格式】
新数列的最短长度。
【样例 1 输入】
5 2
2 2 1 1 2
【样例 1 输出】
3
【样例 1 解释】
1,1,1是一个满足条件的新序列,长度为3。

【数据范围】
测试点	n,m范围
1,2	1≤n≤10,1≤k≤5
3,4	1≤n≤100,1≤k≤10
5,6	1≤n<k≤100
7,8	1≤n≤2*k,1≤k≤10000
9,10	1≤n≤100000,1≤k≤10000

这是我贪心思路的 code QWQ

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int n = 1E5+10; 
int T = 1;
int a[n], ans;
signed main(){
	while(T --){
		int N, K;
		cin >> N >> K;
		ans = N + 1;
		for(int i = 1; i <= N; ++ i) cin >> a[i];
		sort(a + 1, a + N + 1);
		int L = 1;
		for(int i = 2; i <= N; ++ i){
			if(a[i] == a[i - 1]) L ++;
			else{
				ans = min(ans, L);
				L = 1;
			}
		}
		cout << ans + 1;
	}
	return 0;
}





30 分,请问是否需要纠正,感谢

2024/8/18 20:11
加载中...