第二节 基础算法 - 2
例题
逆序对
题目描述
猫猫 TOM 和小老鼠 JERRY 最近又较量上了，但是毕竟都是成年人，他们已经不喜欢再玩那种你追我赶的游戏，现在他们喜欢玩统计。
最近，TOM 老猫查阅到一个人类称之为“逆序对”的东西，这东西是这样定义的：对于给定的一段正整数序列，逆序对就是序列中 \(a_i>a_j\) 且 \(i<j\) 的有序对。知道这概念后，他们就比赛谁先算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。
Update:数据已加强。
输入格式
第一行，一个数 \(n\)，表示序列中有 \(n\)个数。
第二行 \(n\) 个数，表示给定的序列。序列中每个数字不超过 \(10^9\)。
输出格式
输出序列中逆序对的数目。
样例输入 #1
6
5 4 2 6 3 1
样例输出 #1
11
提示
对于 \(25\%\) 的数据，\(n \leq 2500\)
对于 \(50\%\) 的数据，\(n \leq 4 \times 10^4\)。
对于所有数据，\(n \leq 5 \times 10^5\)
请使用较快的输入输出
应该不会 \(O(n^2)\) 过 50 万吧 by chen_zhe
点击查看代码
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 524288
int a[MAXN],tmp[MAXN],n;
long long merge(int a[],int l,int m,int r){
long long step = 0;
int i = l,j = m+1;
for(int k = l;k <= r;k ++){
if((j > r) || (i <= m) && (a[i] <= a[j])) tmp[k] = a[i ++];
else tmp[k] = a[j ++], step += m-i+1;
}
for(int i = l;i <= r;i ++) a[i] = tmp[i];
return step;
}
long long msort(int a[],int l,int r){
if(l >= r) return 0;
int mid = l+(r-l)/2;
return msort(a,l,mid)+msort(a,mid+1,r)+merge(a,l,mid,r);
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
printf("%lld",msort(a,1,n));
return 0;
}
[NOIP2015 提高组] 跳石头
题目背景
一年一度的“跳石头”比赛又要开始了!
题目描述
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 \(N\) 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 \(M\) 块岩石（不能移走起点和终点的岩石）。
输入格式
第一行包含三个整数 \(L,N,M\)，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 \(L \geq 1\) 且 \(N \geq M \geq 0\)。
接下来 \(N\) 行，每行一个整数，第 \(i\) 行的整数 \(D_i( 0 < D_i < L)\)， 表示第 \(i\) 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
一个整数，即最短跳跃距离的最大值。
样例输入 #1
25 5 2
2
11
14
17
21
样例输出 #1
4
提示
输入输出样例 1 说明
将与起点距离为 \(2\)和 \(14\) 的两个岩石移走后,最短的跳跃距离为 \(4\)(从与起点距离 \(17\) 的岩石跳到距离 \(21\) 的岩石,或者从距离 \(21\) 的岩石跳到终点)。
数据规模与约定
对于 \(20\%\)的数据，\(0 \le M \le N \le 10\)。
对于 \(50\%\) 的数据，\(0 \le M \le N \le 100\)。
对于 \(100\%\)的数据，\(0 \le M \le N \le 50000,1 \le L
\le 10^9\)。
点击查看代码
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
inline int read(){
int x=0,w=1 ; char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
return x*w;
}
int l,n,m,a[100005],c,mid,ans;
bool pick_stone(int x){
int last_p = 0,num = 0;
for(int i=1;i<=n;i++){
if(last_p+x > a[i])num++;
else last_p = a[i];
}
if(num>m) return false;
return true;
}
int main(){
l=read();n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
int p=1,r=l;
while(p<=r){
mid = p+(r-p)/2;
if(pick_stone(mid))ans=mid,p=mid+1;
else r=mid-1;
}
cout<<ans;
return 0;
}
[NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
题目描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 \(n-1\) 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 \(1\) ，并且已知果子的种类 数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有 \(3\) 种果子，数目依次为 \(1\) ， \(2\) ， \(9\) 。可以先将 \(1\) 、 \(2\) 堆合并，新堆数目为 \(3\) ，耗费体力为 \(3\) 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 \(12\) ，耗费体力为 \(12\) 。所以多多总共耗费体力 \(=3+12=15\) 。可以证明 \(15\) 为最小的体力耗费值。
输入格式
共两行。
第一行是一个整数 \(n(1\leq n\leq 10000)\) ，表示果子的种类数。
第二行包含 \(n\) 个整数，用空格分隔，第 \(i\) 个整数 \(a_i(1\leq a_i\leq 20000)\) 是第 \(i\) 种果子的数目。
输出格式
一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 \(2^{31}\) 。
样例输入 #1
3
1 2 9
样例输出 #1
15
提示
对于 \(30\%\) 的数据，保证有 \(n \le 1000\)：
对于 \(50\%\) 的数据，保证有 \(n \le 5000\)；
对于全部的数据，保证有 \(n \le 10000\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n, ans = 0;
priority_queue<int, vector<int>, greater<int> > q;
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
int x;
scanf("%d", &x);
q.push(x);
}
while(q.size() > 1) {
int x = q.top(); q.pop();
int y = q.top(); q.pop();
ans += x + y;
q.push(x + y);
}
printf("%d\n", ans);
return 0;
}