首页 > 代码库 > 【尺取法】【Multiset】bzoj1342 [Baltic2007]Sound静音问题
【尺取法】【Multiset】bzoj1342 [Baltic2007]Sound静音问题
O(n)地枚举所有长度为k的段，每次暴力转移。
转移的时候只是从最后插入一个数，从前面删去一个数。
计算的时候要取当前的max和min。
用multiset(∵元素是可重的)以上这些操作都是O(logn)的。
1 #include<cstdio> 2 #include<set> 3 using namespace std; 4 multiset<int>S; 5 multiset<int>::iterator it; 6 int n,m,limit; bool goal; 7 int a[1000001]; 8 int main() 9 {10 scanf("%d%d%d",&n,&m,&limit);11 for(int i=1;i<=n;i++) scanf("%d",&a[i]);12 for(int i=1;i<=m;i++) S.insert(a[i]);13 it=S.end(); it--;14 if((*it)-(*S.begin())<=limit) puts("1"),goal=1;15 for(int i=2;i<=n-m+1;i++)16 {17 S.erase(S.find(a[i-1]));18 S.insert(a[m+i-1]);19 it=S.end(); it--;20 if((*it)-(*S.begin())<=limit) printf("%d\n",i),goal=1;21 }22 if(!goal) puts("NONE");23 return 0;24 }
【尺取法】【Multiset】bzoj1342 [Baltic2007]Sound静音问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。