#55178: 新想法 Binary search (31ms, 3.9mb)
s410011@student.cysh.cy.edu.tw
(yohan0323)
簡單來說，先把日期的vector sort
然後就透過std::lower_bound 求出 第一個 >= min date 的index, 再透過std::upper_bound 求出第一個 > max date 的 index (不可以用lower_bound 因為要分成= 或不等於的兩個case)
然後就加上(max index - min index) 就好了 (不用加一因為max date的index 一定會大1)
片段程式碼如下
.
.
.
.
.
.
.
.
.
.
.
.
int s,e;cin >> s >> e; if(s > max || e<min){ continue;}auto first = lower_bound(date.begin(),date.end(),s), last = upper_bound(date.begin(),date.end(),e);cnt += last-first;