Sorting Device

題目

After being stuck at home for months because of covid, you decided to explore the contents of your parent’s basement. Among numerous useless items, you found one peculiar object - a sorting device from the sixties that was used to teach sorting algorithms. The device consists of N ordered slots that get initialized with distinct integers once the device is turned on, and a screen for tracking cost. As a user, you can perform swap operations. One swap operation allows you to swap elements at positions i and j for a total cost of A∗|i−j|+B, where A,B are parameters written on the back of the device. Since you’ve been studying your sorting algorithms, you definitely know how to sort the numbers with the smallest possible cost. Right?

Input

The first line contains a single integer N (1≤N≤2⋅105 ) - the number of slots the machine has. The next line has N space-separated integers up to 109 in absolute value that the machine generated after you turned it on. The last line has two positive integers A,B from the machine specs. 1≤A,B≤1000.

Output

In the first line, output the smallest cost needed to sort the sequence. In the second line, output K - the number of swaps needed to do that. In the next K lines output the description of the swaps that need to be done. In each line output two numbers - indices of elements to be swapped, separated by a space. Indices start with one. If two or more sequences have the same total cost, you can output any of them.

大緻題意：n個貨物，給你n個數，要求交換後，按大小排列，交換i,j,位置的物品代價為A|I-J|+B 求最小代價，以及交換次數，和交換順序*

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll n,A,B;
	cin>>n;
	vector<int> v(n);
	for(int i=0;i<n;i++) {
		cin>>v[i];
	}
	cin>>A>>B;
	vector<int> sx;
	sx=v;
	sort(sx.begin(),sx.end());
	sx.erase(unique(sx.begin(),sx.end()),sx.end());
	for(int i=0;i<n;i++){
		v[i]=lower_bound(sx.begin(), sx.end(),v[i]) - sx.begin();//在這裡确定目前位置的物品應該放的位置
	}
	 ll cost = 0;
  vector<pair<int,int>>ans;
  auto swp = [&](int x, int y) {//交換函數
    cost += B + A*(y-x);
    ans.emplace_back(x+1, y+1);
    swap(v[x], v[y]);
  };
  for(int x=0;x<n;x++) 
  if(v[x] < x) {//應該向前跳
  //q中必是遞增序列[v[x],x] ;
    vector<int> q ;
	q= {v[x]};
    while(v[q.back()] < x) q.push_back(v[q.back()]);//所謂存去的位置又要去哪 
    q.push_back(x);
    //如果不經過while循環直接交換（x,v[x]）;
    //q保證了不會消耗多餘的成本，相鄰的代價小不會1->3->2反複
    reverse(q.begin(),q.end());//翻轉，不翻轉無法到達應該去的地方 
    for(int i=1;i<(int)(q).size();i++) swp(q[i], q[i-1]);
  }

  cout << cost << endl;
  cout << (int)(ans).size() << endl;
  int len=ans.size();
  for(int i = 0;i < len;i ++) printf("%d %d\n",ans[i].first,ans[i].second);
}