首先要知道每次拿走最小才會達到最優,因為最小的不會給其他的提供任何加分,只有可能減小加分。
刪除卡片的次序確定了,剩下的就是確定每段區間的左右端點。
pos[i] 表示數字 i 在初始序列中的位置。
首先枚舉i (i = 1 -> n),如果不需刪除,則將pos[i]放入set S中,如果不需刪除,則在S中二分查找上下界。
總的時間復雜度為o( (n-k)*log(k) )。
#include
#include
#include
#include
#include
#include
#include
#include
#include