糖糖别胡說，我真的不是簽到題目（字首和）

文章目錄

• 題目
• • 樣例1
• 送出連結
• 解析

題目

題目描述:

從前，有 n 隻萌萌的糖糖，他們分成了兩組一起玩遊戲。他們會排成一排，第 i 隻糖糖會随機得到一個能力值 b i b_i bi​ 。從第 i 秒的時候，第 i 隻糖糖就可以消滅掉所有排在他前面的和他不是同一組的且能力值小于他的糖糖。

為了使遊戲更加有趣，糖糖的爸爸，嬌姐，會發功 m 次，第i次發功的時間為 c i c_i ci​，則在第 c i c_i ci​ 秒結束後， b 1 , b 2 , . . . . . , b c i b_1,b_2,.....,b_{ci} b1​,b2​,.....,bci​ 都會增加 1.

現在，嬌姐想知道在第 n 秒後，會有多少隻糖糖存活下來。

輸入描述:

第一行隻有一個整數 T（T < 6），表示測試資料的組數。

第二行有兩個整數n,m。表示糖糖的個數以及嬌姐發功的次數。 （ 1 ≤ n ≤ 50000 , 1 ≤ m ≤ 1000000 ） （1 \leq n \leq 50000,1 \leq m \leq 1000000） （1≤n≤50000,1≤m≤1000000）

第三行到 n+2 行,每行有兩個整數 a i , b i a_i,b_i ai​,bi​，表示第 i 隻糖糖屬于哪一組以及他的能力值。 （ 0 ≤ a i ≤ 1 , 1 ≤ b i ≤ 1000000 ） （0 \leq a_i \leq 1,1 \leq b_i \leq1000000） （0≤ai​≤1,1≤bi​≤1000000）

第 n+3 行到第 n+m+2 行，每行有一個整數 c i c_i ci​，表示GTW第i次發功的時間。 ( 1 ≤ c i ≤ n ) (1 \leq c_i \leq n) (1≤ci​≤n)

輸出描述:

總共 T 行，第 i 行表示第 i 組資料中，糖糖存活的個數。

樣例1

輸入

1 
4 3 
0 3 
1 2 
0 3 
1 1 
1 
3 
4
           

輸出

送出連結

https://ac.nowcoder.com/acm/problem/14583

解析

最開始想的，外層循環從 1 到 n 枚舉每一個糖糖，碰到發功的時刻 i，對于小于 i 的糖糖戰鬥力++，時間複雜度 n 2 n^2 n2，逾時。

優化：

對于每一個發功的時刻，其前面的糖糖的戰鬥力都要加 1，可以字首和維護第 i 秒時一共發功了多少次。

假設：j<i

編号為j的糖糖的戰鬥力增加了sum[i]-sum[j-1]

編号為i的糖糖的戰鬥力增加了sum[i]-sum[i-1]

若 j 位置的糖糖被i位置的糖糖消去的條件是：

j<i && group[j]!=group[i] && fight[j]<fight[i]

fight[j]=fight[j]+sum[i]-sum[j-1]

fight[i]=fight[i]+sum[i]-sum[i-1]

fight[j]<fight[i]可以轉化為：fight[j]-sum[j-1]<fight[i]-sum[i-1]

細節條件：所有的糖糖要麼是0組的，要麼是1組的。

s[0]，s[1]分别記錄所在組的最大的fight[i]-sum[i-1]

倒着掃描，更新最大值

int s[2];
        s[0]=s[1]=-2e7;  //初始化為最小值
        int res=n;
        for(int i=n; i>=1; i--)
        {
            if(fight[i]<s[group[i]^1])///group[i]^1記錄不同組，因為是倒序的，s[group[i]^1]記錄的是比此時的i大的戰鬥力
                res--;
            s[group[i]]=max(s[group[i]],fight[i]);
        }
           

完整代碼：

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5*1e4+10;
int group[N];
int fight[N];
int sum[N];
int n,m;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d",&group[i],&fight[i]);
            sum[i]=0;
        }
        while(m--)
        {
            int x;
            scanf("%d",&x);
            sum[x]+=1;
        }
        for(int i=1; i<=n; i++)
        {
            sum[i]+=sum[i-1];///字首和 第i秒時一共加了sum[i]次
            fight[i]-=sum[i-1];
        }
        int s[2];
        s[0]=s[1]=-2e7;///初值一定要大
        int res=n;
        for(int i=n; i>=1; i--)
        {
            if(fight[i]<s[group[i]^1])
                res--;
            s[group[i]]=max(s[group[i]],fight[i]);
        }
        printf("%d\n",res);
    }
    return 0;
}