一道带有一点思维的树状数组题目

题目

A magician has a stack of n cards labeled 1 through n, in random order. Her trick involves discarding all of the cards in numerical order (first the card labeled 1, then the card labeled 2, etc.). Unfortunately, she can only discard the card on the top of her stack and the only way she can change the card on the top of her stack is by moving the bottom card on the stack to the top, or moving the top card on the stack to the bottom. The cost of moving any card from the top to the bottom or vice versa is simply the value of the label on the card. There is no cost to discard the top card of the stack. Help the magician calculate the minimum cost for completing her trick.

魔术师有一堆n张牌，按随机顺序标为1到n。她的诀窍包括按数字顺序丢弃所有卡片（首先是标记为1的卡片，然后是标记为2的卡片，等等）。不幸的是，她只能丢弃她牌堆顶部的牌，唯一能改变她牌堆顶部的牌的方法是将牌堆底部的牌移到顶部，或将牌堆顶部的牌移到底部。从上到下或从上到下移动任何卡的成本只是卡上标签的价值。不需要花费弃牌的费用。帮助魔术师计算完成她的魔术的最低成本。

The Problem:

Given the number of cards in the magician's stack and the order of those cards in the stack, determine the minimum cost for her to discard all of the cards.

问题：根据魔术师牌堆中的牌数和牌堆中牌的顺序，确定她丢弃所有牌的最低成本。

The Input:

The first input line contains a positive integer, t, indicating the number of test cases to process. Each test case is on a separate input line by itself and starts with an integer, c (1 ≤ c ≤ 10^5), indicating the number of cards in the stack, followed by c labels for the cards in the stack (starting from the top going to the bottom). Each of these labels will be in between 1 and c, inclusive, and each label will be unique.

第一个输入行包含一个正整数t，表示要处理的测试用例数。每个测试用例单独位于一个输入行上，以一个整数c（1≤c≤10^5）开头，表示堆栈中的卡数，然后是堆栈中卡的c标签（从上到下）。每个标签都在1到c之间（包括1和c），并且每个标签都是唯一的。

The Output:

For each test case, output a single integer on a line by itself indicating the minimum cost for the magician to complete her magic trick.

对于每个测试用例，在一行上单独输出一个整数，表示魔术师完成魔术的最低成本。

样例

2 5 3 5 1 4 2 3 1 2 3

样例

15 0

题意：

给出一个数组，要按照从小到大的顺序删除。但是删除只能在最前面删除，求需要移动的数字和。把数组看作一个串。

1、从前面删，也就是把该数字前面的都逐渐移动到末尾。

2、从后面考虑，就一个一个把后面的移动到前面，紧接着把该数字移动到前面。

那么到这里其实我们需要的是该数字到前一个删除的数字之间还剩下多少个数字A以及全部剩下的数字个减掉A，两者的最小值累加进答案就可以了，主要的一小个难点是判断哪个在前面哪个在后面的操作上。

如果当前位置小于之前删掉的位置，那么

ans+=min(sum(last)-sum(now-1),sum(n)-(sum(last)-sum(now-1))，从后考虑和从前考虑

另外一种情况建议读者自己推算一下。

用树状数组维护一下当前位置前的数字总数，之后删除数字后也从树状数组中删除就好了。

源代码 C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
const int maxn=200010;

int lowbit(int x)
{
 return x&(-x);
}
int n;
long long sum[maxn];
void add(int pos,long long val)
{
 while(pos<=n)
 {
  sum[pos]+=val;
  pos+=lowbit(pos);
 }
}

long long query(int pos)
{
 long long ans=0;
 while(pos>0)
 {
  ans+=sum[pos];
  pos-=lowbit(pos);
 }
 return ans;
}//以上是树状数组
struct node
{
 long long val;int pos;
 bool operator<(const node &n)const{
  return val<n.val;
 }
}no[maxn];

int main()
{
 int cas=1;
 int t;cin>>t;
 while(t--)
 {
  scanf("%d",&n);
  memset(sum,0,sizeof sum);
  for(int i=1;i<=n;i++){
   scanf("%lld",&no[i].val);
   add(i,no[i].val);
   no[i].pos=i;
  }
  long long ans=0;
  int s=n;
  sort(no+1,no+1+n);
  int last=-1;
  for(int i=1;i<=n;i++){
   int pos=no[i].pos;
   if(last==-1){//第一个数字不需要考虑前面的状态
    ans=min(query(n)-query(pos-1),query(pos-1));
   }else {
    if(pos>last){//要转移的位置大于现在最前面的位置
     ans+=min(query(pos-1)-query(last),query(n)-query(pos-1)+query(last));
    }else {//与上面相反
     ans+=min(query(last-1)-query(pos-1),query(n)-query(last-1)+query(pos-1));
    }
   }
   last=pos;
   add(pos,-no[i].val);
  }
  cout<<ans<<endl;

 }
}

温馨提示

如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请关注ACM算法日常。