#39432: 思路


s10900156@nhsh.tp.edu.tw (ShanC)

學校 : 臺北市立內湖高級中學
編號 : 138785
來源 : [36.225.80.7]
最後登入時間 :
2024-03-31 09:07:17
e313. 最少相異字母 -- 2018年10月APCS | From: [36.225.10.9] | 發表日期 : 2024-02-20 23:57

每一次迴圈讀入字串 str

由於字母只有 26 個 (INT_MAX = 2^31),所以這樣的大小可以開個 int cnt 假裝是一個 bitset 然後用 cnt |= (1 << (str[i] - 'A')) 寫進去 cnt

接下來開個由小到大的 priority_queue ,裡面擺 pair 放 __builtin_popcount(cnt) 與 str ,其中__builtin_popcount(cnt) 就是計算 cnt 中 1 的數量的函數

藉由 priority_queue 會自動幫忙排好順序的性質,直接取 top() 就可以直接得到答案

 
ZeroJudge Forum