HackerRank "New Year Chaos"
2024-08-26 15:43:46
Two tricks here:
1. Counting no. of inversed pairs - using Merge Sort, nothing special
2. How to check 'chaotic'? We simply check if any number is over 2 slots away from its own slot : )
#!/bin/python3 import sys ret = 0
def merge(arr1, arr2):
global ret
if not arr1: return arr2
if not arr2: return arr1
for v2 in arr2:
arr1.append(v2)
i = len(arr1) - 1
while(i > 0):
if arr1[i] < arr1[i - 1]:
arr1[i - 1],arr1[i] = arr1[i], arr1[i - 1]
i -= 1
ret += 1
else:
break
return arr1 def mergeSort(arr):
n = len(arr)
if (n < 2): return arr
return merge(mergeSort(arr[:n//2]), mergeSort(arr[n//2:])) T = int(input().strip())
for _ in range(T):
ret = 0
n = int(input().strip())
q = [int(q_temp) for q_temp in input().strip().split(' ')]
# your code goes here
bTooCh = False
for i in range(n):
if q[i] - i > 3:
bTooCh = True
break
if bTooCh:
print ("Too chaotic")
continue mergeSort(q)
print (ret)
最新文章
- PhpStorm 快捷键大全 PhpStorm 常用快捷键和配置
- css笔记1: html页面的CSS、DIV命名规则
- CSDDN特约专稿:个性化推荐技术漫谈
- bootstrap插件思路整理
- 基于Java的WebSocket推送【转载】
- 【转】APP被苹果App Store拒绝的N个原因(持续补充)
- DNS (二)协议
- [BJOI2019]删数(线段树)
- 清北学堂学习总结day2
- css_属性
- Windows 版 SourceTree 免登录跳过初始设置的方法
- 守护进程(Daemon)
- 获取请求Url
- Javaweb学习笔记——(七)——————myexlipse基本使用、jdk5.0新特性及反射讲解
- hdu3183 rmq求区间最值的下标
- canvas 写一个刮刮乐抽奖
- Varnish 入门
- 400 bad Request: JackSon将json串转成List<;Object>;,异常com.fasterxml.jackson.databind.JsonMappingException
- Android App的签名
- linux中rc.d目录下的文件