记录编号	584999	评测结果	AAAAAAAAAA
题目名称	3937.[YNOI2019] 排序	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	1.966 s
提交时间	2023-11-17 22:33:36	内存使用	83.56 MiB

#include<bits/stdc++.h>
using namespace std;
int t,n;
long long a[100010],b[100010],s,c[10000010],ma=0;
long long ask(long long x)
{
	long long ans=0;
	for(;x;x-=x&-x) 
	{
		ans=max(ans,c[x]);
	}
	return ans;
}
void add(long long x,long long y)
{
	for(;x<=10000000;x+=x&-x)
	{
		c[x]=max(c[x],y); 
	}
}
int main()
{
	freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
	cin>>t;
	while(t--)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		s=0;
		ma=0;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			s+=a[i];
			ma=max(ma,a[i]);
		} 
		for(int i=1;i<=n;i++)
		{
			b[i]=a[i]+ask(a[i]);
			add(a[i],b[i]);
		}
		cout<<s-ask(ma); 
	}
	return 0;
}