洛谷P6033 [NOIP2004 提高组] 合并果子 加强版 （单调队列）

数据加强了，原来nlogn的复杂度就不行了......

首先对原来的n个数排序（注意不能用快排），因为值域是1e5，所以可以开桶排序，开两个队列，一个存原来的n个数（已经满足单增），另一队列存两两合并后的数（也是满足单调性的），每次合并从两个队列中选取最小的两个数，合并后放入第二个队列就行了。

更难的题目还是蚯蚓，其中隐晦的单调性与此类似。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define int long long

 4 queue<int>q1;

 5 queue<int>q2;

 6 int n,to[100005];//to[]是桶

 7

 8 int read(){

 9     int x=0,f=1;char c=getchar();

10     while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}

11     while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();

12     return x*f;

13 }

14

15 signed main(){

16     n=read();

17     for(int i=1;i<=n;i++){

18         int a;a=read();

19         to[a]++;

20     }

21     for(int i=1;i<=100000;i++){

22         while(to[i]){

23             to[i]--;

24             q1.push(i);

25         }

26     }

27     int ans=0;

28     for(int i=1;i<=n-1;i++){//合并n-1次

29         int x,y;

30         if((q1.front()<q2.front()&&!q1.empty())||q2.empty()){

31             x=q1.front();

32             q1.pop();

33         }

34         else{

35             x=q2.front();

36             q2.pop();

37         }

38         if((q1.front()<q2.front()&&!q1.empty())||q2.empty()) {

39             y=q1.front();

40             q1.pop();

41         }

42         else{

43             y=q2.front();

44             q2.pop();

45         }

46         ans+=x+y;

47         q2.push(x+y);

48     }

49     printf("%lld\n",ans);

50     return 0;

51 }

洛谷P6033 [NOIP2004 提高组] 合并果子 加强版 （单调队列）的相关教程结束。