我覺得這個評測機和我有仇,寫了read+getchar都會超時這么多,最后好像是ios::sync_with_stdio(false);惹的禍...

昨天想找一些水題來寫,就看到了這個模擬"水題",想了一下午都不知道怎么搞.

已知一些牛的顏色和位置,求連續相同顏色或連續兩種顏色數量相同的區間右端點位置減左端點位置最長的距離.復雜度小于n^2.

(果然還是我太菜了,而且只會二分,對于這種題就很難搞.)

首先,這道題的答案不滿足單調性,尺寸并不是在一個值之后就全部能取到的那種.所以不能寫二分.

但是本題是一個模擬啊,不要想的那么恐怖.

先sort一下.

連續相同顏色只要從前向后掃一遍就好.

數量相同的話,對于每一個牛可以求出前綴和,維護一個數組記錄前綴和i第一次出現的位置wei[i](在原結構體數組中的位置),如果當前前綴和數組上沒有值,就把自己記錄下來.否則可以用它來更新答案:ans=max(ans,o[i].x-o[wei[sum]+1].x);

這個過程中sum可能會變成負數,可以先把sum賦值成>=n的數,同時注意wei數組的大小.

wei[0]一定是0,為了區分0,更新過的和未更新過的,可以寫一個循環使數組賦值為-1,然后寫一句話:wei[sum]=0后再開始循環.

?

using namespace std; inline int read() {int x=0,f=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}return x*f; } int i,f; char b; int n,ans,sum; int wei[300001]; struct cow {int x,t; }o[100010]; inline bool Orz(cow a,cow b) {return a.x<b.x; } int main() {n=read();for(i=1;i<=n;++i){o[i].x=read();b=getchar();if(b=='G') o[i].t=1;else o[i].t=-1;}sort(o+1,o+1+n,Orz);for(i=1;i<=n;++i){for(f=i+1;o[f].t==o[i].t&&f<=n;++f){}f--;ans=(ans>o[f].x-o[i].x?ans:o[f].x-o[i].x);i=f;}for(i=0;i<=200000;++i)wei[i]=-1;sum=100000;wei[sum]=0;for(i=1;i<=n;++i){sum+=o[i].t;if(wei[sum]==-1)wei[sum]=i;elseans=(ans>o[i].x-o[wei[sum]+1].x?ans:o[i].x-o[wei[sum]+1].x);}cout<<ans; }

?

轉載于:https://www.cnblogs.com/qywyt/p/9680359.html

總結

以上是生活随笔為你收集整理的p1968的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。