这题刚开始没想到可以枚举第二个客栈,选择了枚举第一个客栈.

因为只有一次询问,所以每个客栈最低消费的绝对值是没有意义的,有意义的只有这个客栈的最低消费与p的相对大小.

那么可以用1代表最低消费小于等于p,0代表大于p,对这个数组进行一次前缀和,那么这个前缀和就是一个具有单调性的数组.

这样枚举第一个客栈之后,可以用二分在logn时间内寻找出第一家可以喝咖啡的客栈,这家客栈之后的所有与第一家客栈色调相同的客栈都可以作为第二家客栈.

nlogn的最长不上升子序列

nlogn的最长不上升子序列虽然不难,也很常用,但是很容易打错,一不注意就把变量名打错了.

主要思想是用二分优化"寻找a[j]>=a[i]中f[j]最大的j"

for(int i = 1;i <= N;i++)
{
    int maxx = -INF;
    for(int j = 1;j < i;j++)//优化这个循环
    {
        if(a[j] >= a[i])maxx = max(maxx,f[j]);
    }
    f[i] = (maxx == INF)?1:maxx+1;
}

既然使用二分,就要寻找一个有单调性的东西.

P3933 Chtholly Nota Seniorious

题目背景

大样例下发链接: https://pan.baidu.com/s/1nuVpRS1 密码: sfxg

こんなにも、たくさんの幸せをあの人に分けてもらった

だから、きっと

今の、私は

谁が何と言おうと

世界一、幸せな女の子だ

基础算法

贪心

根据贪心的数学背景我们在做贪心题目的时候一般有两种策略： 1.把一个问题划分成很多子问题，对于每个子问题直接求最优解，然后合成一个最优解； 2.对于当前局面，搜索所有可能的“临近局面”，选择最优的局面进行转移