CF競(jìng)賽題目講解_CF777E(樹(shù)狀數(shù)組+離散化)
2022-08-05 10:59 作者:Clayton_Zhou | 我要投稿
?https://codeforces.com/problemset/problem/777/e
題意
給出一堆指環(huán)的內(nèi)徑a、外徑b、高h(yuǎn)，要把指環(huán)疊成塔，
即外徑從下往上不遞增，同時(shí)兩個(gè)上下相鄰的指環(huán)中上面的指環(huán)
的外徑要大于下面指環(huán)的內(nèi)徑（不然上面的指環(huán)就掉下去了），
求最高的塔。
思路
將所有a(i)的內(nèi)外半徑排序，并且離散化為單調(diào)數(shù)組，也就是拿單調(diào)離散數(shù)組的下標(biāo)去映射a[i]。然后就只需要用樹(shù)狀數(shù)組 維護(hù)區(qū)間最大高度。
input
3
1 5 1
2 6 2
3 7 3
標(biāo)簽：
