前言

题目难度适中，但是总体比较灵活，需要转一些弯。模拟题的话，需要仔细处理，否则很容易出错。（由刷题的小菜鸡提供）

第一题

小红需要n个不同的魔法药剂，她可以从商店以ai的价格购买第i种红色版本魔法药剂，也可以用两种其他的红色版本药剂配置蓝色版本 小红想知道，她最少需要花多少钱才能得到1到n个不同的魔法药剂，蓝色或者红色都可以。

输入描述

第一行输入一个整数n，表示魔法药剂数量。

第二行输入n个整数ai，表示第i种红色版本魔法药剂的价格。

接下来n行，每行两个整数bi和ci，表示用第 bi 种和第 ci 种红色版本魔法药剂配置第 i 种蓝色版本魔法药剂。

1<= n <=1e5

1<= ai <=1e4

1<= bi,ci <= n

输出描述

输出一个整数，表示最少需要花多少钱才能得到1到n个不同的魔法药剂，蓝色或者红色都可以。

示例1

输入

5
2 4 10 1 3

输出

16

说明

红色药剂的价格分别为[2, 4, 10, 1, 3]

蓝色药剂的价格分别为[14, 4, 6, 7, 3]

配置第三种蓝色药剂，其他都购买红色药剂花费 16。

思路与代码：

模拟，哪种做法便宜选哪个

#include<bits/stdc++.h>
using namespace std;
using gg = long long;

int main() {
 gg n; cin >> n;
 vector<gg> red(n);
 vector<gg> price(n, 1000005);
 for(int i = 0; i < n; i++) {
  cin >> red[i];
 }
 vector<vector<gg>> blue(n, vector<gg>(2));
 for(int i = 0; i < n; i++) {
  cin >> blue[i][0] >> blue[i][1];
  blue[i][0]--; blue[i][1]--;
 }
 //sort(red.begin(), red.end());
 for(int i = 0; i < n; i++) {
  price[i] = min(red[i], red[blue[i][0]] + red[blue[i][1]]);
 }
 gg ans = 0;
 for(auto x : price) ans += x;
 cout << ans << endl;
 return 0;
}

第二题

小红有一个长度为n的数组。如果存在一个长度为3的子数组，使得a_i <= a_i+1 <= a_i+2，那么这个数组就是有趣的。每次操作可以修改数组的一个值，请问最少需要几次操作才能使得这个数组变得不有趣

输入描述

第一行输入一个整数n，表示数组的长度。第二行输入几个整数a1, a2，···，an，表示数组的初始值。

1<= n <=1e5    1<= ai <= 1e9

输出描述

输出一个整数，表示答案

示例

输入

5
6 2 4 5 1

输出

1

思路与代码

贪心+找规律

首先找出所有连续的有趣子数组，记录其长度；

对于递增子数组，可以通过将其中间的数改为一个较大值进行破坏，可以证明破坏边缘不如破坏中间；

长度为3，需要1次；

长度为4，需要1次；

长度为5，相当于破坏1次+长度为3；

长度为6，相当于破坏一次+长度为4；

找规律为 破坏次数 = （(连续递增子数组长度 - 1 ) / 2），累加就行了

#include<bits/stdc++.h>
using namespace std;
using gg = long long;

int main() {
 gg n; cin >> n;
 vector<gg> arr(n);
 for(int i = 0; i < n; i++) cin >> arr[i];
 vector<gg> nums;
 gg len = 1, ans = 0;
 for(int i = 1; i < n; i++) {
  if(arr[i] >= arr[i-1]) len++;
  else {
   if(len >= 3) nums.push_back(len);
   len = 0;
  }
 }
 if(len >= 3) nums.push_back(len);
 for(auto x : nums) ans += (x-1) / 2;
 cout << ans << endl;
 return 0;
}

第三题

小红有一个长度为 n 的排列，她每次可以选择两个数ai和aj，要求i和j的奇偶性相同，然后交换这两个数。问最少需要多少次操作才能使得数组变成有序的，如果不能变的有序，输出-1。

输入描述

第一行输入一个整数n，表示数组的长度

第二行输入n个整数 a1,a2，.,an，表示数组的元素。

1 <= n <= 1e5

1 <= ai <= n

输出描述

如果能变成有序的，输出最少需要的操作次数，否则输出-1.

示例

输入

5
1 4 5 2 3

输出

2

说明

需要交换a2,a4和a3,5，得到[1, 2, 3, 4, 5]

思路与代码：

奇偶分组+任意交换让数组变有序的最小操作

首先判定能否完成，对奇偶分组进行排序再合并，与原数组排序后对比，如果不相等代表不能完成；

在能完成情况下，就是分开算奇偶数组变有序的最小操作；

具体做法是跟排序后的对比，建立值到索引的映射，找出循环节个数，总长度-循环节个数就是最小交换次数

经过验证，题目中的有序是代表升序，尝试过降序反而会错。

#include<bits/stdc++.h>
using namespace std;
using gg = long long;


gg mer(vector<gg> &a) {
 auto b = a;
 sort(b.begin(), b.end());
 unordered_map<gg, gg> mp;
 gg len = a.size();
 for(int i = 0; i < len; i++) mp[b[i]] = i;
 gg loops = 0;
 vector<bool> flag(len, false);
 for(int i = 0; i < len; i++) {
  if(!flag[i]) {
   gg j = i;
   while(!flag[j]) {
    flag[j] = true;
    j = mp[a[j]];
   }
   loops++;
  }
 }
 return len - loops;
}


int main() {
 gg n; cin >> n;
 vector<gg> arr(n);
 for(int i = 0; i < n; i++) cin >> arr[i];
 vector<vector<gg>> jiou(2);
 for(int i = 0; i < n; i++) jiou[i % 2].push_back(arr[i]);
 auto ou = jiou[0], ji = jiou[1];
 sort(ji.begin(), ji.end());
 sort(ou.begin(), ou.end());
 vector<gg> sorted(n);
 sort(arr.begin(), arr.end());
 for(int i = 0; i < n; i++) {
  if(i % 2 == 0) sorted[i] = ou[i/2];
  else sorted[i] = ji[i/2];
 }
 if(arr != sorted) {
  cout << -1 << endl;
  return 0;
 }
 gg ans = mer(jiou[1]) + mer(jiou[0]);
 cout << ans << endl;
 return 0;
}