法一：前缀和

时间复杂度：o(n)

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
int n;
const int N =100010;
int a[N];
LL s[N];
LL maxv;
int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    s[i]=s[i-1]+a[i];//前缀和数组
    int k=1;//层数
    LL maxs=-2e9,bid=1;//分别存放最大值和最大值对应的下标
    while((1<<(k-1))<=n)//只要左端点<=n,就继续做
    {
        LL l=(1<<(k-1)),r=((1<<k)-1);//l和r分别代表每一层的左右端点
        if(r<=n)
        maxv=max(maxs,s[r]-s[l-1]);
        else maxv=max(maxs,s[n]-s[l-1]);//如果右端点超过n，就直接算以n为右端点的前缀和
        if(maxv>maxs)
        {
            bid=k;
            maxs=maxv;
        }
        k++;
    }
    cout<<bid<<endl;
    return 0;
}

法二：双指针

时间复杂度：i,j两个指针加起来只遍历一次整个数组，o(n)

C++代码

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;
using namespace std;
int n;
const int N =100010;
int a[N];
LL maxv=-2e9,bid;
int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(int i=1,d=1;i<=n;i*=2,d++)//i枚举每一层的起点下标，d枚举层数
    {
        LL s=0;
        for(int j=i;j<i+(1<<(d-1))&&j<=n;j++)//j不能越界j<=n
        {
            s+=a[j];
        }
        if(s>maxv)
        {
            bid=d;
            maxv=s;
        }
    }
    cout<<bid<<endl;
    return 0;
}

m = int(input())
N = 100010
tt = 0
stk = [0] * N
for _ in range(m):
    op, *p = input().split()
    if op == 'push':
        x = int(p[0])
        stk[tt] = x
        tt += 1
    elif op == 'pop':
        tt -= 1
    elif op == 'empty':
        if tt:
            print('NO')
        else:
            print('YES')
    else:
        print(stk[tt-1])

题目描述

一家神秘餐馆准备开放N天，牛牛 和 牛妹听到这个消息后，准备尽可能多的一起去吃午饭
餐馆有M道菜，牛牛和牛妹每次来只允许点一道菜，如果在第i天买了第j道菜
那么第i+7天也只能买第j道菜
第i天第j道菜的价格为price[i][j]
‘0’-‘9’代表0-9美元
‘A’-‘Z’代表10-35美元
‘a’-‘z’代表36-61美元

牛牛和牛妹一共只有budget美元，请问他们最多可以吃几天的午饭

输入描述:

第一行输入3个整数n,m,budget (1 ≤ n ≤ 50, 1 ≤ m ≤ 50, 0 ≤ budget ≤ 10000)
接下来n行每行输入一个字符串，包含m个字符
第i行的第j个字符表示第i天第j道菜的价格

输出描述:

输出一个整数
示例1

输入

7 2 13
26
14
72
39
32
85
06

输出

5

算法1

(暴力) 只能过掉一半的样例，不仅超时而且有答案错误的测试点

#include<iostream>
#include<map>
using namespace std ;

const int N = 55 ;

int n , m , money ;
int g[N][N] ;
int res ;

bool vis[N][N]  ;


/**
dfs 思路
首先判断这一天我是不是被注定买啥菜了，
-------------如果是，那就做出相应的操作，然后继续递归
*/

void dfs(int day ,int remain) 
{
    if(remain <= 0)   // 已经买不起了
    {
        res = max(res , day- 1) ;

        return ;
    }

    if(day > n && remain >= 0)   //  全都吃过了，而且钱还有剩余
    {
        res = n ;
        return ;
    }
    int choice = -1;
    for(int i = 0 ; i < m ; i ++) 
    {
        if(vis[day%7][i]) 
        {
            choice = i ;
            break ;
        }
    }


    if(choice != -1) 
    {
        if(remain>=g[day][choice])
        {
             dfs(day+1,remain-g[day][choice]) ;
        }else // 如果买不到注定的菜，那就返回吧
        {
            res = max(day-1,res) ;
            return ;
        }

    }
    else  // choice 没被注定，说明这是前七天 
    {
        bool flag = 0 ;
        for(int i = 0 ; i < m ; i ++) 
        {

            if(remain >= g[day][i] )  // 如果买得起，那就继续买
            {

                flag = 1 ;
                vis[day][i] = 1 ;  // 进行标记
                dfs(day+1 , remain-g[day][i]) ;  
                vis[day][i]= 0 ;  // 恢复现场
            }
        }
        if(!flag) //都买不起了 
        {
            res = max(res , day -1  ) ;

            return ;
        }
    }


}

int main()
{
    cin >> n >> m >> money ;
    for(int i = 1 ; i <= n ; i ++) 
    {
        for(int j = 0 ; j < m ; j ++) 
        {
            char t ;
            cin >> t ;
            if( t >= '0' && t <= '9')
            {
                g[i][j] =  t-'0';
            }
            else if(t >= 'A' && t <= 'Z') 
            {
                g[i][j] = t - 'A' + 10 ;
            }
            else 
            {
                g[i][j] = t - 'a' + 36 ;
            }
        }
    }
    dfs(1,money) ;
    cout << res << endl;
    return 0 ;
}

算法2

看了人家的代码写的，这看起来像dp（虽然数组叫dp），但我看来更像是一个预处理打表而已，核心还是暴力

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 55 ;

int g[N][N] ;
int dp[N][N] ;
int buy[N] ;
int n , m , budget ;

int main()
{
    cin >> n >> m >> budget ;

    for(int i = 1 ; i <=n ; i ++  ) 
    {
        for(int j  = 0 ; j < m ; j ++) 
        {
            char t ;
            cin >> t ;
            if( t >= '0' && t <= '9')
            {
                g[i][j] =  t-'0';
            }
            else if(t >= 'A' && t <= 'Z') 
            {
                g[i][j] = t - 'A' + 10 ;
            }
            else 
            {
                g[i][j] = t - 'a' + 36 ;
            }
        }
    }

    for(int i = 1 ; i <=n ; i ++) 
    {
        for(int j = 0 ; j < m ; j ++) 
        {
            if(i <= 7 ) 
            {
                dp[i][j] = g[i][j] ;
            }
            else 
            {
                dp[i][j] = dp[i-7][j] + g[i][j] ;
            }
        }
    }

    for(int i = 1 ; i <= n ; i ++ ) 
    {
        if(i >= 8) 
        {
            budget += dp[i-7][buy[i-7]] ;
        }
        int min = 0x3f3f3f3f ;
        for(int j = 0 ; j < m ; j ++) 
        {
            if(min > dp[i][j])
            {
                min = dp[i][j] ; // 挑出当天的最便宜的饭菜
                buy[i] = j ;
            }
        }
        if(i == n && min <= budget) 
        {
            cout << n << endl;
        }
        if(min > budget) 
        {
            cout << i-1 << endl; 
            break ;
        }
        else
        {
            budget -= min ;
        }
    }

    return 0 ;
}

原题链接：0到n-1中缺失的数字

题解：

题目意思：

有一个递增序列，有n个数字,每个数字都在[0~n] 中(共n+1个数字)。
原数组：只有n个数字，但是对应的数字范围数组却有[0~n],n+1个数字，
其中原数组相对于 数据范围数组，少了一个数字，找出它

例如：
[0] ：有1个数字 , 每个数字都在[0,1]之间。即，数字范围数组[0,1] , 缺失数字1
[1] : 有1个数字 , 每个数字都在[0,1]之间。即，数字范围数组[0,1] , 缺失数字0
[0,1,2] : 有3个数字，每个数字，都在[0,3]之间。即，数字范围数组[0,1,2,3] , 缺失数字3
[0,1,3] : 有3个数字，每个数字，都在[0,3]之间。即，数字范围数组[0,1,2,3] , 缺失数字2

思路：

1、按照题目意思 , nums 第i个位置 上的数字，应该就是 i ,即 如果i == nums[i]
2、当 i != nums[i] , 证明，数字i缺失
3、当循环一遍，都没发现有数字缺失，这个数字没有被比较，但是又在[0 ~ nums.size()]之间,
那么缺失的数字，就是 for循环没有遍历到的数字：nums.size() 。

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        for(int i = 0 ; i<nums.size() ; i++ ) //遍历数字： 0 ~ nums.size()-1 
        {
            if(nums[i] != i) return i;//当 nums[i] != i , 证明数字i不在nums里面，输出
        }
        // 当找不到缺失的数字，证明，最后一个数字是缺失的,
        // 比如 [0，1] ，有2个数据，应该包含 0 ~ 2 中所有数字,即数字范围数组[0，1，2] 
        // 0，1 都小于 nums.size() ,已经被遍历过了，还是找不到缺失数字，那么这个数字就是 nums.size()
        return nums.size();
    }
};

题目描述

农夫约翰一直难以让他种植的植物茁壮成长，他需要你来给植物适当的浇水。

给定二维平面中 N 个雨滴的位置，其中 y 表示雨滴的垂直高度，x 表示其在一维数轴上的位置。

每个雨滴以每秒 1 个单位长度的速率向下（朝 x 轴）下落。

你需要将宽度为 W 的农夫约翰的花盆沿 x 轴放置在某处，以便第一个雨滴击中花盆与最后一个雨滴击中花盆之间的时间差至少为 D（使得花盆中的花获得充足的水）。

一滴水落在花盆的边缘就等于击中了花盆。

给定 D 的值和 N 个雨滴的位置，请计算 W 的最小可能值。

样例

输入：

4 5
6 3
2 4
4 10
12 15

输出：

2

解释

将宽度为 2 的花盆放置在 x=4..6 处，可以接到雨滴 1 和 3，两雨滴接到的时间差为 10−3=7。

算法1

(暴力枚举 w ,二分答案优化) $O(nlogn)$

推荐楼下题解

算法2

(尺取法+单调队列优化) $O(n)$

1. 按照x排序，尺取
2. 查找最大值&最小值时用单调队列维护

分析

尺取法，一般是在给的具有单调性的数据中找到不大于某一个上限的“最优连续子序列” 。
其实一般能用二分做的都大概率能用尺取法做（时间复杂度不同而已）
而找某段区间最大值与最小值就自然想到了单调队列

C++ 代码

#include<bits/stdc++.h>

using namespace std;

long long n,k,qmax[1000005],qmin[1000005],ans=10000000;
int tax=0,hax=1,tin=0,hin=1;

struct dd
{
    long long x,y;
}p[1000005];

bool cmp(dd a,dd b)
{   return a.x<b.x;   }

long long work()
{
    int i=1;
    for(int j=1;j<=n;j++)
    {       
        while(hax<=tax&&p[j].y>p[qmax[tax]].y) tax--;
        qmax[++tax]=j;
        while(hin<=tin&&p[j].y<p[qmin[tin]].y) tin--;
        qmin[++tin]=j;
        while(p[qmax[hax]].y-p[qmin[hin]].y>=k)//满足题意，找最短 
        {
            ans=min(ans,(p[j].x-p[i].x));//记录答案 
            i++;
            while(hax<=tax&&qmax[hax]<i) hax++;
            while(hin<=tin&&qmin[hin]<i) hin++;
        }
    }
    if(ans==10000000)
    return -1;
    else
    return ans;
}


int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
    sort(p+1,p+1+n,cmp);
    cout<<work();

    return 0;
}