鏈接：https://ac.nowcoder.com/acm/contest/8282/B
題意
有一個叫雪糕之王的家伙要吃雪糕，
雪糕之王每次吃雪糕時會選定一個區間[L，R]，從左向右吃雪糕，
假如雪糕之王第 i 個吃掉的雪糕和上一個吃掉的型別相同，那么 雪糕之王 的愉悅值不會提升，否則愉悅值會 +1，
例如，當選定區間為1 1 2 3時，雪糕之王的愉悅度為3（有連續的相同種類雪糕1 1）；
而當選定區間的雪糕為1 2 3 4 時，大王的愉悅度為4，
當雪糕大王吃第一塊雪糕時愉悅度一定+1，（這個很好理解，每個區間內的第一塊雪糕一定會讓大王愉悅度+1）
第一行給出三個數字n（雪糕的個數），k（愉悅度），p（區間數），
第二行給出n個數字，分別代表每塊雪糕的種類，
接下來的p行中，每行給出兩個數字L，R（代表從第L塊雪糕開始吃，到第R個雪糕結束），
對于每個區間，請問大王吃完雪糕后愉悅度是否能達到k，能輸出Yes，不能則輸出No，
資料范圍
思路
在A題把我憋死之后，我把希望就放在了B題上，
首先看了一下題之后，注意到資料和時間限制，就感覺這題已經不能暴力了，
這道題的做法就是建立一個h陣列，h[i]代表的是在第i個數字之前（包含第i個數字），有多少對相鄰且相同的數字，
h[1]=0; //第一個數字對應的h[1]=0（就1個數字）
for(int i=2; i<=n; i++)
{
if(a[i]==a[i-1])
h[i]=h[i-1]+1;
else
h[i]=h[i-1];
}
然后對于每個輸入的區間，我們先假設沒有相鄰一樣的雪糕，愉悅度就應該是s-l+1，
然后我們再看一下這個區間里有多少對相鄰一樣的，減去就好，
ans-=(h[r]-h[l]);
直接放代碼，「伊麗莎白」！
代碼
//這里不要用cin，會T掉
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+50;
int a[maxn],h[maxn];
int n,k,q,l,r;
int main()
{
scanf("%d%d%d",&n,&k,&q);
for(int i=1; i<=n; i++)
scanf("%d",&a[i]);
h[1]=0;
for(int i=2; i<=n; i++)
{
if(a[i]==a[i-1])
h[i]=h[i-1]+1;
else
h[i]=h[i-1];
}
for(int i=1; i<=q; i++)
{
scanf("%d%d",&l,&r);
int ans=r-l+1;
ans-=(h[r]-h[l]);
if(ans<k)
printf("No\n");
else
printf("Yes\n");
}
}
倒霉的一天，從壞心情開始，到沒爆0結束，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/207021.html
標籤：其他
上一篇：C語言小游戲2——掃雷