快排
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int n, k;
int quick(int l, int r, int k){
if(l == r) return q[r];
int x = q[l + r >> 1], i = l - 1, j = r + 1;
while(i < j){
while(q[ ++ i] < x);
while(q[ -- j] > x);
if(i < j) swap(q[i], q[j]);
}
int len = j - l + 1;
if(k <= len) return quick(l, j, k);
else return quick(j + 1, r, k - len);
}
int main(){
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
printf("%d\n", quick(0, n - 1, k));
return 0;
}
逆序对
#include<iostream>
#include<cstring>
#include<algorithm>
typedef long long LL;
using namespace std;
const int N = 5e5 + 10;
int n;
LL q[N], tmp[N];
LL merge_sort(int l, int r){
if(l >= r) return 0;
int mid = l + r >> 1;
LL res = merge_sort(l, mid) + merge_sort(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r){
if(q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else{
tmp[k ++ ] = q[j ++ ];
res += mid - i + 1;
}
}
while(i <= mid) tmp[k ++ ] = q[i ++ ];
while(j <= r) tmp[k ++ ] = q[j ++ ];
for(int i = l, j = 0; i <= r; i ++ , j ++ ) q[i] = tmp[j];
return res;
}
int main(){
while(cin >> n, n){
for(int i = 0; i < n; i ++ ) scanf("%lld", &q[i]);
printf("%lld\n", merge_sort(0, n - 1));
}
return 0;
}
790数的三次方根
#include<iostream>
using namespace std;
double n;
const double eps = 1e-8;
bool check(double x){
return x * x * x >= n;
}
int main(){
scanf("%lf", &n);
double l = -100, r = 100;
while(r - l > eps){
double mid = (l + r) / 2;
if(check(mid)) r = mid;
else l = mid;
}
printf("%.6lf\n", r);
return 0;
}
797差分
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], n, m, b[N];
void insert(int l, int r, int c){
b[l] += c;
b[r + 1] -= c;
}
int main(){
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for(int i = 1; i <= n; i ++ ) insert(i, i, a[i]);
while(m -- ){
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
insert(l, r, c);
}
for(int i = 1; i <= n; i ++ ) a[i] = a[i - 1] + b[i];
for(int i = 1; i <= n; i ++ ) printf("%d ", a[i]);
return 0;
}