CF1579E2. Array Optimization by Deque
题意
给一组数据放入deque中(可以从前面放,也可以从后面),要使逆序数最少。
解法
可以发现,前面的放入顺序对后面的每一个数产生的逆序数没有影响。所以直接贪心,每个数选择最好的位置放进去。注意要离散化。
#include <bits/stdc++.h>
#define int long long
#define lb(x) (x&(-x))
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=800005;
int t,n,a[N],tt[N],f[N];
void add(int x) {
for(int i=x;i<=N;i+=lb(i)) f[i]++;
}
int query(int x) {
int ans=0;
for(int i=x;i;i-=lb(i)) ans+=f[i];
return ans;
}
signed main() {
cin>>t;
while(t--) {
memset(f,0,sizeof f);
cin>>n;
For(i,1,n) {
cin>>a[i];
tt[i]=a[i];
}
sort(tt+1,tt+n+1);
int m=unique(tt+1,tt+n+1)-tt-1;
For(i,1,n) a[i]=lower_bound(tt+1,tt+m+1,a[i])-tt;
int ans=0;
For(i,1,n) {
ans+=min(query(a[i]-1ll),(i-1)-query(a[i]));
add(a[i]);
}
cout<<ans<<'\n';
}
}
//3 5 5 6 7 9
//adding 6
//front->3 back->2
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1000005;
int t,n,d,mx;
struct node {
int v,s;
} a[N];
queue <int> q;
signed main() {
cin>>t;
while(t--) {
memset(a,0,sizeof a);
cin>>n>>d;
For(i,0,n-1) cin>>a[i].v;
while(!q.empty()) q.pop();
mx=0;
For(i,0,n-1) if(a[i].v==0 && a[(i-d+n)%n].v==1) {
q.push(i);
}
while(!q.empty()) {
int now=q.front();
q.pop();
if(a[(now-d+n)%n].v==1) {
a[(now-d+n)%n]=(node) {0,a[now].s+1};
q.push((now-d+n)%n);
mx=max(mx,a[now].s+1);
}
}
bool flag=1;
For(i,0,n-1) if(a[i].v==1) flag=0;
if(flag==1) cout<<mx<<'\n'; else puts("-1");
}
return 0;
}
//f[i][j]:到i位且当前距离左端点j时,到右端点的长度
//太难了太难了 动态规划一生之敌
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=10005;
int t,n,a[N],f[N][2005],mx;
signed main() {
cin>>t;
while(t--) {
cin>>n;
mx=0;
For(i,1,n) {cin>>a[i]; mx=max(mx,a[i]);}
For(i,1,n) For(j,0,2*mx) f[i][j]=0x3f3f3f3f;
f[0][0]=0;
For(i,0,n-1) For(j,0,2*mx) {
f[i+1][max(0,j-a[i+1])]=
min(f[i+1][max(0,j-a[i+1])],f[i][j]+a[i+1]);
if(j+a[i+1]<=2000) f[i+1][j+a[i+1]]=
min(f[i+1][j+a[i+1]],max(f[i][j]-a[i+1],0));
}
int ans=0x3f3f3f3f;
For(i,0,2*mx) ans=min(ans,i+f[n][i]);
cout<<ans<<'\n';
}
return 0;
}
人间没有永恒的夜晚,世界没有永恒的冬天