題目鏈接：點擊查看

題目大意：現(xiàn)在玩猜數(shù)字游戲，如果猜的數(shù)字比答案要大，就輸出 ' + ' ，比答案小，就輸出 ' - ' ，猜中了答案，輸出 ' . '，?給出這樣的 n 條指令，問最多有多少條指令可以同時保證正確性

題目分析：感覺蠻不錯的一道差分題目，分類討論一下：

' . ' ：當(dāng)前指令只對 pos 位置的數(shù)做出了貢獻(xiàn)

' + ' ：當(dāng)前指令對 [ -inf , pos - 1 ] 內(nèi)的數(shù)做出了貢獻(xiàn)

' - ' ：當(dāng)前指令對 [ pos + 1 , inf ] 內(nèi)的數(shù)做出了貢獻(xiàn)

因為數(shù)據(jù)是離散化的，可以用 map 來維護(hù)，也可以離散化一下，時間復(fù)雜度都是 nlogn 級別的

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const LL inf=0x3f3f3f3f3f3f3f3f;const int N=1e5+100;map<LL,int>mp;void update(LL l,LL r) {mp[l]++,mp[r+1]--; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++){int pos;char op[5];scanf("%d%s",&pos,op);if(op[0]=='.')update(pos,pos);else if(op[0]=='+')update(-inf,pos-1);elseupdate(pos+1,inf);}int sum=0,ans=0;for(auto it:mp){sum+=it.second;ans=max(ans,sum);}printf("%d\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客 - 二分(差分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。