2019-10-01笔记

贪心

贪心算法是指，贪心算法是指，在对问题求解时总做出当前看来最好的选择。 贪心算法是指，在对问题求解时总做出当前看来最好的选择。 也就是说，不从整体最优上加以考虑他所做出的在某种意义局 也就是说，不从整体最优上加以考虑他所做出的在某种意义局部最优解。

P1080

一看最大值最小先想二分。

我们考虑两个相邻的人$x$和$y$，看交换他们是否会变得更优。

设$S=a_1 a_2⋯a_{x-1}$，则$v_{x_1}=\lfloor\cfrac{S}{b_x}\rfloor,v_{y_1}=\lfloor\cfrac{Sa_x}{b_y}\rfloor$。

如果把这两个人交换一下，那么 $v_{x_2}=\lfloor\cfrac{S_{a_y}}{b_x}\rfloor,v_{y_2}=\lfloor\cfrac{S}{b_y}\rfloor$。

除了这两个人之外，其他所有人的奖赏都不会发生改变，所以我们只需要考虑$max(v_{x_1},v_{y_1})$和$max(v_{x_2},v_{y_2})$的大小关系即可。

而我们发现$v_{x_1} \leq v_{x_2},v_{y_2} \leq v_{y_1}$，所以我们其实只需要比较$v_{x_2}$和$v_{y_1}$。

$v_{x_2}

也就是说$a_i b_i$较小的要排在前面。

所以直接按照$a_ib_i$排序就可以了。注意统计答案需要高精度。

P3045

• 能用优惠卷一定用。
• 能买便宜就不买贵。
• 先取$C_i$最小的前$k$个作为答案，这一部分物品定会在最终的答案里。

然后我们考虑用剩下的钱买物品。分两种情况：

• 下一个不用优惠卷则补偿差价$p_i$
• 下一个用优惠卷，答案加上$c_i+min(p_j-c_j)$

CF1214C

移动左括号等价移动右括号。

当然，也可以把最左边的右括号移动到最右，判断时候合法。

$$Ans=\sum_{i=1}^k(S_{p_i}-S_{p_{i-1}})=S_{p_1}+2P_2-2S_{p_1}+3S_{P_3}-3S_{p_2}+\cdots+kS_{p_k}-kS_{p_{k-1}}=kS_n-\sum_{i=1}^{k-1}S_{p_i}$$

也就是说我们只需要把整个数组求一前缀和，然后在$n−1$个里面选 个里面选择最大的$k−1$个减去，得到的就是最小值。

CF1213F

考虑拓扑排序。

套路

考虑相邻两个元素，看交换它们是否会使得答案变更优。 经典模型是你需要按照一定顺序考虑所有的元素，决最后答案。 经典模型是你需要按照一定顺序考虑所有的元素，决定最后答案。

如果发现贪心发现原来的策略不是最优，可以考虑实现可以撤销的贪心。

二分

二分有二分查找，二分答案等。

P2698

二分区间长度，然后单调队列扫。

搜索

枚举全排列

时间复杂度：$O(n!)$

int a[15];
bool flag[15];
void dfs( int step ) {
    if ( step > n )
        return;
    for ( int i = 1; i <= n; i++ ) {
        if ( flag[i] )
            continue;
        a[step] = i;
        flag[i] = 1;
        dfs( step + 1 );
        flag[i] = 0;
    }
}

枚举子集

时间复杂度：$O(2^n)$

void dfs( int step ) {
    if ( step > n )
        return;
    flag[step] = 1;
    dfs( step + 1 );
    flag[step] = 0;
    dfs( step + 1 );
}
for ( int s = 0; s < ( 1 << n ); s++ ) {
    //do something.
}

枚举子集的子集

时间复杂度：$O(3^n)$

for ( int s = 0; s < ( 1 << n ); s++ )
    for ( int t = s; t; t = ( t - 1 ) & s ) {
        //do something.
    }

其他提及的内容

• multiset
• 0/1分数规划
• 参见0/1分数规划