fork download
copy 
  1. import math
  2. def find(u, par):
  3.  
  4.     if par[u] != u:
  5.         par[u] = find(par[u], par)
  6.     return par[u]
  7.  
  8. def union(u, v, par, size):
  9.     u_root = find(u, par)
  10.     v_root = find(v, par)
  11.  
  12.     if u_root == v_root:
  13.         return 
  14.  
  15.  
  16.     if size[u_root] < size[v_root]:
  17.         par[u_root] = v_root
  18.         size[v_root] += size[u_root]
  19.     else:
  20.         par[v_root] = u_root
  21.         size[u_root] += size[v_root]
  22.  
  23. def ip():
  24.     return map(int,input().split())
  25.  
  26.  
  27.  
  28.  
  29. T=1
  30. T=int(input())
  31. for __ in range(T):
  32.     # n,m=ip()
  33.     # b=[]
  34.     # for _ in range(m):
  35.     #     l,w,h=ip()
  36.     #     b.append(sorted((l,w,h)))
  37.  
  38.     # lst=[1,2]
  39.     # while len(lst)<n:
  40.     #     lst.append(lst[-1]+lst[-2])
  41.     # res=[0 for _ in range(m)]
  42.  
  43.     # for i in range(m):
  44.     #     l,w,h=b[i]
  45.     #     if l>=lst[-1] and w>=lst[-1] and h>=lst[-1]+lst[-2]:
  46.     #         res[i]=1
  47.  
  48.     # print("".join(str(x) for x in res))
  49.  
  50.     n=int(input())
  51.     lst=list(ip())
  52.  
  53.     dic={}
  54.     l=0
  55.     st=-1
  56.     for i in range(n):
  57.         if i==0:
  58.             l=1
  59.             st=i
  60.             continue
  61.  
  62.         if lst[i]==lst[i-1]:
  63.             l+=1
  64.         else:
  65.             if lst[i-1] not in dic:
  66.                 dic[lst[i-1]]=[]
  67.             dic[lst[i-1]].append((st,st+l-1))
  68.             l=1
  69.             st=i
  70.     if lst[n-1] not in dic:
  71.         dic[lst[n-1]]=[]
  72.     dic[lst[n-1]].append((st,st+l-1))
  73.  
  74.     # print(dic)
  75.     mn=float('inf')
  76.     for i in dic:
  77.         l=dic[i]
  78.         sm=sum(j[1]-j[0]+1 for j in l)
  79.         mn=min(mn,i*(n-sm))
  80.     print(mn)
Success #stdin #stdout 0.12s 14064KB
comments (?)
stdin
copy 
3
4
2 4 1 3
3
1 1 1
10
7 5 5 5 10 9 9 4 6 10
stdout
copy 
3
0
35
https://ideone.com/czR9d4
language:
Python 3 (python  3.12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!