C. Stable Groups Div.2

5371 ワード
2021.07.01 テキストリンク
https://codeforces.com/contest/1539/problem/C
1秒、256 MBメモリ
input :
  • n, k, x (1≤n≤200000, 0≤k≤10^18)
  • a1,a2,…,an (1≤ai≤10^18)
    • output :
  • In the only line print a single integer: the minimum number of stable groups you can split the students into.
    • 最小グループ数
  • を出力してください.
    • 条件:

  • A group of students is called stable, if in the sorted array of their levels no two neighboring elements differ by more than x .

  • グループの学生が安定しているといえば、ソートにおける隣接する2つの要素の違いはx未満でなければならない.

  • teachers can invite at most k additional students with arbitrary levels (at teachers' choice)
  • k人の学生を追加することができます.(オプション)
    • まず配列を並べ替えて、何個以上のグループが必要かを求め、入力した配列自体だけで安定したグループを作成できます.また、このユーザ(cntと呼ばれる)kよりも大きいと、条件を満たすことができないため、さらなるグループ化が必要となる.
    グループ化する場合は、追加していないユーザでも良いので、cntから値を減算します.そしてこの値をkと比較し、k以下の場合を探し出し、その場合のグループ数が正解となる.
    最初に優先順位キューを使用して追加したユーザを記述した結果、時間の複雑さに問題が発生しました.リストを人数の多い部分(リストを並べ替えて一番後ろから)から削除する方法で、時間の複雑さを満たします.
    最後尾から最終完了点までの差異はグループの個数を表していると考えられる.
    人が増えるごとにグループが増えるからといっていいでしょう.
    import sys

n, k, x = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))
temp = []
data.sort()

cnt = 0
for i in range(1, len(data)):
    term = (data[i] - data[i - 1] - 1) // x
    if term > 0:
        temp.append(term)
        cnt += term

temp.sort()
idx = len(temp) - 1
while cnt > k:
    cnt -= temp[idx]
    idx -= 1

print(len(temp) - idx)
    Django RESTful API
    [プログラマー]ランキング