結果
問題 |
No.1425 Yet Another Cyclic Shifts Sorting
|
ユーザー |
![]() |
提出日時 | 2025-06-12 14:53:23 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 818 bytes |
コンパイル時間 | 176 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 126,592 KB |
最終ジャッジ日時 | 2025-06-12 14:56:32 |
合計ジャッジ時間 | 10,545 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 WA * 31 |
ソースコード
import bisect def main(): import sys input = sys.stdin.read().split() n = int(input[0]) A = list(map(int, input[1:n+1])) # 创建包含值和原始索引的列表 with_index = [(A[i], i+1) for i in range(n)] # 索引从1开始 # 按值排序 with_index.sort() # 构建pos数组,记录排序后的元素在原数组中的位置 pos = [idx for (val, idx) in with_index] # 计算最长递增子数组的长度 def length_of_lis(nums): tail = [] for x in nums: idx = bisect.bisect_right(tail, x) if idx == len(tail): tail.append(x) else: tail[idx] = x return len(tail) max_len = length_of_lis(pos) print(n - max_len) if __name__ == "__main__": main()