2022-08-30-之江实验室笔试-1h两题100%

// 最多AK人数
// 时间限制： 1000MS
// 内存限制： 65536KB
// 题目描述：
//        招聘季又到了，各公司的线上笔试又要开始了，已知某公司十分缺人手，他们希望尽可能多的人可以进入复试。而进入复试的条件只有一个，就是线上笔试拿到满分。
//        已知在该公司的题库***有m道题，编号为从1到m，一共有n个人会参加笔试。该公司的笔试分为两场，请你将这m道题分成两套，每套题至少有一道，每道题都要使用。
//        已知这n个人每个人能解出的题目编号都是连续的若干道题，我们用“L R”的方式描述，表示某个人可以解出第L道题到第R道题。
//        每个人只要在其中一场笔试拿到满分就可以进入复试。请问最多有多少人可以进入复试。
// 输入描述
//         输入第一行包含两个正整数n和m(1<=n<=50000,1<=m<=100000);
//         接下来有n行，每行有两个正整数L_i和R_i，表示第i个人可以解出第L_i题到第R_i题。
// 输出描述
//         输出仅包含一个整数，表示最多有多少人可以进入复试。

// 样例输入
// 4 8
// 4 7
// 1 4
// 5 8
// 2 5
// 样例输出
// 3

// #include<iostream>
// #include<vector>
// using namespace std;

// int main(){
//   int n,m;cin>>n>>m;
//   // vector<vector<int>> c(n,vector<int>(2));
//   // for(int i=0;i<n;i++){
//   //   cin>>c[i][0]>>c[i][1];
//   // }
//   //sort(c.begin(),c.end());
//   vector<int> d(m+2,0);
//   int l,r;
//   for(int i=0;i<n;i++){
//     cin>>l>>r;
//     d[l]+=1;
//     d[r+1]--;
//   }
//   int c=0;
//   int maxc=1;
//   for(int i=1;i<=m;i++){
//     c+=d[i];
//     if(maxc<c)
//       maxc=c;
//   }
//   cout<<maxc;
//   return 0;
// }

// 糖果屋
// 时间限制： 1000MS
// 内存限制： 65536KB
// 题目描述：
//       万圣节要到了，小朋友们要来要糖果了，糖果店为了打广告，举办了这样一个活动，前n+1个索要糖果的小朋友都是可以拿到糖果的，每一个小朋友都至少要发一块糖果，但是还有一个抽卡环节，糖果店准备了n张卡，前n个小朋友会分别取一张，卡片有两种，第一种是‘+’，抽到这张卡就意味着，下一个小朋友拿到的糖果比自己多，第二种是‘-’，抽到这张卡意味着，下一个小朋友拿到的糖果比自己少。
//        糖果店的糖果是在前n个小朋友都抽完卡以后统一发放的，请问糖果屋最少发放多少糖果，才能符合抽卡的结果。
// 输入描述
// 输入第一行仅包含一个正整数n，表示卡片的数量。(1<=n<=500000)
// 输入第二行是一个长度为n的字符串，仅包含“+，-”两种符号。
// 输出描述
// 输出仅包含一个正整数，表示糖果店最少发出的糖果数量。

// 样例输入
// 3
// --+
// 样例输出
// 8

// 提示
// 最少的发放糖果的方案是{3，2，1，2}

// O(n) 空间
// #include <iostream>
// #include <vector>
// using namespace std;

// int main()
// {
//     int n;
//     cin >> n;
//     string s;
//     cin >> s;
//     // n=3;s="+--";
//     vector<int> f(n + 1, 0);
//     f[0] = 1;
//     int ans = 1;

//     int c_ = 0;
//     int cp = 0; // debug1: 本来没有cp和lastPlus这一套流程跟踪最后一个加法后的值
//     int lastPlus = 0;
//     for (int i = 0; i < s.length(); i++)
//     {
//         if (s[i] == '+')
//         {
//             f[i + 1] = f[i] + 1;
//             ans += f[i + 1];
//             if (c_ == 0)
//                 cp++;
//             else
//             {
//                 cp = 1; // debug3: 本来是1，36%
//                 c_ = 0;
//             }
//         }
//         else
//         {
//             f[i + 1] = 1;
//             if (cp > 0)
//             {
//                 lastPlus = f[i] - 1; // 最后一个加号对应的值-1（可以减多少次）
//                 cp = 0;
//             }
//             else
//             {
//                 if(lastPlus==0)
//                 {
//                     c_++;
//                 }
//             }
//             lastPlus--; // bug2：本来只放在了上面的if里
//             c_++;
//             ans += c_;
//         }
//     }
//     cout << ans;
//     return 0;
// }

// O（1）空间
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    string s;
    // cin >> n>>s;
    n=5;s="+--++";
    // vector<int> f(n + 1, 0);
    // f[0] = 1;

    int fi=1;
    int ans = 1;

    int c_ = 0; // 减法次数
    int cp = 0; //cp表示加法次数，debug1: 本来没有cp和lastPlus这一套流程跟踪最后一个加法后的值
    int lastPlus = 0; // 最后一个加法后的值
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == '+')
        {
            // f[i + 1] = f[i] + 1;
            fi=fi+1;
            // ans += f[i + 1];
            ans+=fi;
            if (c_ == 0)
                cp++;
            else
            {
                cp = 0; // debug3: 本来是1，36%
                c_ = 0;
            }
        }
        else
        {
            // f[i + 1] = 1;
            if (cp > 0)
            {
                // lastPlus = f[i] - 1; // 最后一个加号对应的值-1（可以减多少次）
                lastPlus = fi-1; // 可以减这么多次
                cp = 0;
            }
            else
            {
                if(lastPlus==0)
                {
                    c_++;
                    // lastPlus--; bug2
                }
            }
            fi=1;
            lastPlus--; // bug2：本来只放在了上面的if里
            c_++;
            ans += c_;
        }
    }
    cout << ans;
    return 0;
}