法一:前缀和

时间复杂度: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;
}



四舍五入
12分钟前
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])



以凝
16分钟前

题目描述

一家神秘餐馆准备开放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 ;
}


新鲜事 原文

cly1
18分钟前
AcWing【AC之星】教育优惠计划!https://www.acwing.com/user/security/school_verify/ac_stars/ 我的邀请码是:HDCIX 有哪位大佬填写一下我的邀请码给点AC币吗……呜呜……我的AC币少得可怜啊

图片



Fphoenix
19分钟前

原题链接: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();
    }
};


新鲜事 原文

caocao666
21分钟前
有大佬会做第二题吗,我做的是360m,但答案是320m 一辆汽车以某一速度正对山崖匀速行驶,鸣笛2s后听到回声,汽车从鸣笛到司机听到回声前进了40m,已知声音在空气中的传播速度为340m/s,求: 1.汽车行驶的速度 2.鸣笛处到山崖的距离


新鲜事 原文

不言
22分钟前
AcWing《寒假每日一题2022》拼团优惠!https://www.acwing.com/activity/content/introduction/88/group_buy/42849/



音乐盒
25分钟前

题目描述

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

给定二维平面中 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;
}


新鲜事 原文

SongGG
26分钟前
AcWing《寒假每日一题2022》拼团优惠!https://www.acwing.com/activity/content/introduction/88/group_buy/42848/


新鲜事 原文

兴_Lu
27分钟前
AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/42840/ 还差一个人勒