排序不等式

排序不等式在刷acwing的时候碰到了一个，感觉还是挺新奇并且有用的一个东西

 简记：顺序和（两者都是升序）>=乱序和>=逆序和

证明的话就不证了，百度上都有

来总结一下两个例题：

1.排队打水：https://www.luogu.com.cn/problem/P1223

这道题还是蛮经典的，经典贪心

也很模板，求最小时间，就让时间大小从小到大排列，然后id从n到1排序相乘求平均数即可，很符合逆序和最小的排序不等式

AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define int long long 
 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 5 const int N=1e3+10;
 6 int n;
 7 struct node
 8 {
 9     int t;
10     int id;
11 }a[N];
12 double ans;
13 bool cmp(node c,node b)
14 {
15     return c.t<b.t;
16 }
17 signed main()
18 {
19     IOS;
20     cin>>n;
21     for(int i=1;i<=n;i++)
22     {
23         cin>>a[i].t;
24         a[i].id=i;
25     }
26     sort(a+1,a+1+n,cmp);
27     for(int i=1;i<=n;i++)
28     cout<<a[i].id<<" ";
29     cout<<endl;
30     for(int i=1;i<=n;i++)
31     {
32         ans+=(double)(a[i].t*((n-i)*1.0));
33     }
34     printf("%.2f\n",ans/(n*1.0));
35     return 0;
36 }

第十三届蓝桥杯省赛C++C组：重新排序

分析：

这道题还是蛮难做的，在acwing上刷的时候看出来了是差分，但不会排序不等式，就g了

也是很明显的排序不等式

设c为每个ai被求和的次数，a为原数组，被求和次数越多的肯定得放越大的数（可用邻项交换证明）。

根据排序不等式原理要求最大值必须是两者都为升序（有一方为降序则为最小值）
以说在处理完l,r区间的时候对差分数组和权值进行排序保证二者对应元素升序相乘
最后求差值即可

AC代码：

 1 //设c为每个ai被求和的次数，a为原数组，被求和次数越多的肯定得放越大的数（可用邻项交换证明）。
 2 //根据排序不等式原理要求最大值必须是两者都为升序（有一方为降序则为最小值）
 3 //所以说在处理完l,r区间的时候对差分数组和权值进行排序保证二者对应元素升序相乘
 4 //最后求差值即可
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 #define int long long 
 8 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 9 const int N=1e5+10;
10 int a[N];
11 int c[N];//每个a[i]被求和次数
12 int n,m;
13 int sum1;
14 int sum2;
15 signed main()
16 {
17     IOS;
18     cin>>n;
19     for(int i=1;i<=n;i++)
20     cin>>a[i];
21     cin>>m;
22     while(m--)
23     {
24         int l,r;
25         cin>>l>>r;
26         c[l]++;
27         c[r+1]--;
28     }
29     for(int i=1;i<=n;i++)
30     {
31         c[i]+=c[i-1];
32         sum1+=c[i]*a[i];
33     }
34     sort(c+1,c+1+n,greater<int>());
35     sort(a+1,a+1+n,greater<int>());
36     for(int i=1;i<=n;i++)
37     {
38         sum2+=c[i]*a[i];
39     }
40     cout<<sum2-sum1<<endl;
41     return 0;
42 }

还有两个蓝书上的题，我还没做到，估两天估计就更了。