[CF1601C]Optimal Insertion

2024-03-16 22:38
文章标签 optimal insertion cf1601c

本文主要是介绍[CF1601C]Optimal Insertion,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Optimal Insertion

题解

怎么一群人都可以在考场上切这道题呀

首先,我们观察到一个性质,我们最终得到的序列 c c c中,来自 b b b的元素的顺序一定是升序的,即权值不递减。
显然,对于 b i > b j b_{i}>b_{j} bi>bj b i b_{i} bi的最优决策点一定不会在 b j b_{j} bj的左边,该性质在我们下面的转移过程中可以见得。
我们考虑加入 b i b_{i} bi时,将 b i b_{i} bi插入在 a j a_{j} aj后面时会贡献的逆序对数 c o s t j = ∑ k = 1 j [ a k > b i ] + ∑ k = j + 1 n [ a k < b i ] cost_{j}=\sum_{k=1}^{j}[a_{k}>b_{i}]+\sum_{k=j+1}^{n}[a_{k}<b_{i}] costj=k=1j[ak>bi]+k=j+1n[ak<bi]
显然,我们在 b i b_{i} bi变大的过程中, ∑ k = j + 1 n [ a k < b i ] \sum_{k=j+1}^{n}[a_{k}<b_{i}] k=j+1n[ak<bi]会不断变大, ∑ k = 1 j [ a k > b i ] \sum_{k=1}^{j}[a_k>b_i] k=1j[ak>bi]会不断变小。
而由于 c o s t j − 1 cost_{j-1} costj1肯定包含 c o s t j cost_{j} costj ∑ k = j + 1 n [ a k < b i ] \sum_{k=j+1}^{n}[a_k<b_i] k=j+1n[ak<bi],所以 c o s t j − 1 cost_{j-1} costj1 ∑ k = j + 1 n [ a k < b i ] \sum_{k=j+1}^{n}[a_k<b_i] k=j+1n[ak<bi]部分增加速度肯定快于 c o s t j cost_{j} costj
同理, c o s t j − 1 cost_{j-1} costj1 ∑ k = 1 j [ a k > b i ] \sum_{k=1}^{j}[a_k>b_i] k=1j[ak>bi]部分的减小速度也一定慢于 c o s t j cost_{j} costj
c o s t j cost_{j} costj的增长速度是慢于 c o s t j − 1 cost_{j-1} costj1,所以我们的最优决策点是不断右移的。
很显然,我们可以用双指针加线段树维护我们的 c o s t cost cost值的变化,对于每个 b i b_{i} bi都加上最小的 c o s t cost cost即可。
时间复杂度 O ( n log ⁡ n ) O\left(n\log\,n\right) O(nlogn)
注意维护原来 a a a序列的逆序对数。

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL;       
const int INF=0x3f3f3f3f;       
const int mo=998244353;
const int inv2=499122177;
const int jzm=2333;
const int zero=10000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<LL,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1LL)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1LL;}return t;}
int n,m,b[MAXN],T,tr[MAXN<<2],lzy[MAXN<<2],sum[MAXN];pii a[MAXN];LL ans;
void build(int rt,int l,int r){lzy[rt]=tr[rt]=0;if(l==r)return ;int mid=l+r>>1;build(lson,l,mid);build(rson,mid+1,r);tr[rt]=min(tr[lson],tr[rson]);
}
void pushdown(int rt){if(!lzy[rt])return ;tr[lson]+=lzy[rt];lzy[lson]+=lzy[rt];tr[rson]+=lzy[rt];lzy[rson]+=lzy[rt];lzy[rt]=0;
}
void modify(int rt,int l,int r,int al,int ar,int aw){if(l>r||l>ar||r<al||al>ar)return ;if(al<=l&&r<=ar){tr[rt]+=aw;lzy[rt]+=aw;return ;}int mid=l+r>>1;pushdown(rt);if(al<=mid)modify(lson,l,mid,al,ar,aw);if(ar>mid)modify(rson,mid+1,r,al,ar,aw);tr[rt]=min(tr[lson],tr[rson]);
}
void insert(int pos){while(pos)sum[pos]++,pos-=lowbit(pos);}
int query(int pos){int res=0;while(pos<=n)res+=sum[pos],pos+=lowbit(pos);return res;}
signed main(){read(T);while(T--){read(n);read(m);ans=0;for(int i=1;i<=n;i++)read(a[i].fir),a[i].sec=i;for(int i=1;i<=m;i++)read(b[i]);sort(a+1,a+n+1);sort(b+1,b+m+1);build(1,0,n);for(int i=1;i<=n;i++)modify(1,0,n,i,n,1);for(int i=1,j=1,k=1;i<=m;i++){for(;a[k].fir<=b[i]&&k<=n;k++)modify(1,0,n,a[k].sec,n,-1);for(;a[j].fir<b[i]&&j<=n;j++)modify(1,0,n,0,a[j].sec-1,1);ans+=1ll*tr[1];}for(int i=1;i<=n;i++)sum[i]=0;for(int i=1,j=1;i<=n;i++){while(a[j].fir<a[i].fir)insert(a[j].sec),j++;ans+=1ll*query(a[i].sec);}printf("%lld\n",ans);}return 0;
}

谢谢!!!

这篇关于[CF1601C]Optimal Insertion的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/816949

相关文章

Insertion Sort Integer Array Insertion Sort Linked List

Sort Integer Array using Insertion sort. //********************************************************************************************************/* Insertion Sort 原理:就是前面的sort部分全部是相对值,从后面拿一个元素,然后跟

innovus:如何让部分sink长到target insertion delay的长度

我正在「拾陆楼」和朋友们讨论有趣的话题,你⼀起来吧? 拾陆楼知识星球入口 来自星球提问: 参考命

leetcode 刷题之路 27 Insertion Sort List

Sort a linked list using insertion sort. 利用插入排序对一个链表进行排序。 插入排序是将待排序的序列分为部分,分别为有序的部分和无序的部分,排序时每次从无序的部分取出一个元素插入到有序的部分中合适的位置,初始时,有序部分只有一个元素,该元素自有序。根据这个思想,并为了方便起见,我们创建一个头结点dummyHead存储排序后的链表,初始阶段,该链表中只存储

uva1349 Optimal Bus Route Design 费用流,二分图匹配

题意:n个景点和一些路径,找到任意数目的路径,路径是一个环,使每个景点仅属于一个环,使权值最小。 分析:每个景点的入度和出度都是1,拆分每个景点u,u',若输入u-v,建立u-v'的边,是一个二分图,若存在完美匹配,说明存在若干个环使每个景点属于其中一个环。增加一个起点s和终点t,边权为费用,所有边的容量都为1,求最小费用最大流,若flow==节点数,存在完美匹配,cost即为答案。 #i

UVA | Optimal Binary Search Tree

原题 题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=514&page=show_problem&problem=1245 Given a set S = (e1, e2, …, en) of n distinct elements such that e1 < e2 < …

UVA 12295 Optimal Symmetric Paths(spfa+记忆化)

题意: 求从左上角到右下角的最短路径数,且要求沿斜线对称 思路: 既然要求对称,所以我们将对称的权值叠加,那么就是求到对角线的最短路径了,通过dp解决方案数 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#include <algorithm>#include <iostream>

553. Optimal Division 最优除法

https://leetcode-cn.com/problems/optimal-division/description/ 思路:x1/x2/…/xn,无论在之间加多少个括号,x1总是作为被除数,x2总是作为除数,因此结果最大的做法是将x3到xn的所有除法转换为乘法,即x1/(x2/…/xn)=x1/x2*x3*…*xn. string optimalDivision(vector<int>

插入排序(Insertion_sort)

最简单的一种排序 基本思想就是从第一个元素开始,每次排列一个元素,一直排列到结尾 例如: 3  1  4  5  7  2  6 第一个元素不用排序,从第二个开始 因为3  >  1所以直接将3覆盖到1上 3  3  4  5  7  2  6 而1用一个变量先存储着 就这样一直覆盖,直到找到比1小或者到最开头为止 然后结束循环的位置就是这个元素的位置 结束循环位置是0在,则赋

Direct Insertion

直接插入排序是稳定的排序,时间复杂度为O(n^2) #include<iostream>using namespace std;void sorting(int arr[],int n){for(int i = 1;i < n;i++){if(arr[i] >= arr[i-1])continue;int current = arr[i];int j;for(j = i-1;j >= 0

leetcode No147. Insertion Sort List

Question: Sort a linked list using insertion sort. Algorithm: 新建一个链表,模仿插入排序的过程 Accepted Code: /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;*