牛客国庆day3
给定一个序列,如果在$a_i$之前有$a_j<a_i$,那么找到最小的$a_j$,把所有这样的$a_j$相加。
1 | 4 |
例如样例就是1前面的2,加上3前面的4。答案为6。
比赛的时候只想到了权值线段树解法,离散化之后维护区间最小值:
1 | struct node |
码量挺大的,看到他们的过题速度就知道事情不简单,其实直接用set存前面所有数,二分查找即可:
1 | set<int> st; |
有$n$种花,每种花有$a_i$种,$m$种不同的话可以组成一束花,问最多可以组成多少种花。
赛时用一个小顶堆一个大顶堆维护第k大,wa+tle七发之后瞎猜了一个结论改改过了。赛后发现别人都是二分,(明天一定补。
1 | priority_queue<int, vector<int>, greater<int>> q1; |