归并排序求解数组中的逆序对 简单分析：因为归并排序会不断把一个数组分成两个数组[L,mid], [mid+1, r]，然后再递归一层一层排序，合并两个子数组，根据这个性质可以发现：  我们可以将逆序对分为三大类，以归并排序的mid分割开来。 第一大类为[l,mid]区间的，第二大类为[mid+1，r]之间的。第三类为一个在左区间，一个在右区间。 前两类的结果则为ll res = merge_sort(l, mid) + merge_sort(mid + 1, r);而第三类的结果则可以在归并数组两个数组的过程中找到。令q[i]为左边，q[j]为右边。我们发现若q[i] > q[j]，则左...

#include<iostream> #include<string> using namespace std; class MyList{ public: struct Link{//建立一个链表 int val; struct Link* next; Link(int _val):val(_val),next(nullptr){} }; MyList(){ dummy = new Link(0);//建立一个虚结点，便于操作头节点。 size = 0;//计算链表中节点的个数。 } void insert(int n,int val) { Link* newnode...

```/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ ListNode* reverse(ListNode* head)//反转链表，模拟实际加法，从低位往高位...

#include<bits/stdc++.h> using namespace std; int main() { int n,v; cin >> n >>v; vector<int>weight(n),value(n); for(int i = 0;i <= n;i++) cin >> weight[i] >> value[i]; vector<int>dp(v+1,0),dp2(v+1,INT_MIN);//dp2[v]指能否装满，如果装满则它的结果发生变化，否则装不满。 dp2[0] = 0;//初...

```#!/bin/bash sum=0 i=1 read n for ((i=1;i<=n;i++)) do read m sum=$(($sum+$m)) done echo "scale=3;$sum/$n" | bc

#include<bits/stdc++.h> using namespace std; int main() { int n; int v; cin >> v; cin >> n;//dp[v]的意思为：容量为v时，能装的最大体积。 vector<int>dp(v+1,0);//本质还是01背包问题，剩余空间最小就是价值最大的意思。01背包算出能装最多的空间， vector<int>volum(n);//再用v-dp[v]就得剩下的最小空间。 for(int i = 0;i < n;i++) cin >> volu...

#include<bits/stdc++.h> using namespace std; int main() { int n,m; cin >> n >>m; vector<vector<int> >arr(n,vector<int>(m)); for(int i = 0;i < n;i++) { for(int j = 0;j < m;j++) { cin >> arr[i][j]; } } vector<vector<int> >dp(n,vector<int&g...