pku 1804
归并排序
/*
* poj1804.c
*
* Created on: 2011-9-29
* Author: bjfuwangzhu
*/
#include<stdio.h>
#define nmax 1010
int num[nmax], temp[nmax];
int res;
void merge(int left, int mid, int right) {
int i, j, k;
i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (num[j] < num[i]) {
temp[k++] = num[j++];
res += mid - i + 1;
} else {
temp[k++] = num[i++];
}
}
while (i <= mid) {
temp[k++] = num[i++];
}
while (j <= right) {
temp[k++] = num[j++];
}
for (i = 0, j = left; j <= right; j++, i++) {
num[j] = temp[i];
}
}
void mergeSort(int left, int right) {
int mid;
if (left < right) {
mid = (left + right) >> 1;
mergeSort(left, mid);
mergeSort(mid + 1, right);
merge(left, mid, right);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int t, n, i, j;
scanf("%d", &t);
for (i = 1; i <= t; i++) {
scanf("%d", &n);
for (j = 0; j < n; j++) {
scanf("%d", num + j);
}
res = 0;
mergeSort(0, n - 1);
printf("Scenario #%d:\n%d\n", i, res);
if (i < t) {
printf("\n");
}
}
return 0;
}
树状数组
//C 树状数组
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define nmax 1010
#define lowbit(x) x&(-x)
typedef struct node {
int val, id;
} node;
node Node[nmax];
int sum[nmax], num[nmax];
void update(int i, int val, int n) {
while (i <= n) {
sum[i] += val;
i += lowbit(i);
}
}
int getSum(int i) {
int res;
res = 0;
while (i > 0) {
res += sum[i];
i -= lowbit(i);
}
return res;
}
int cmp(const void *a, const void *b) {
node n = *(node *) a;
node m = *(node *) b;
return n.val - m.val;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int t, n, temp, i, j, k, res;
scanf("%d", &t);
for (i = 1; i <= t; i++) {
scanf("%d", &n);
for (j = 0; j < n; j++) {
scanf("%d", &Node[j].val);
Node[j].id = j;
}
qsort(Node, n, sizeof(Node[0]), cmp);
memset(sum, 0, sizeof(sum));
num[Node[0].id] = 1, k = 1, temp = Node[0].val;
for (j = 1; j < n; j++) {
if (temp != Node[j].val) {
temp = Node[j].val;
num[Node[j].id] = ++k;
} else {
num[Node[j].id] = k;
}
}
for (j = n - 1, res = 0; j >= 0; j--) {
update(num[j], 1, n + 1);
res += getSum(num[j] - 1);
}
printf("Scenario #%d:\n%d\n", i, res);
if (i < t) {
printf("\n");
}
}
return 0;
}
//C++ 树状数组
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define nmax 1010
#define lowbit(x) x&(-x)
struct node {
int val, id;
bool operator<(const node &m) const {
return val < m.val;
}
};
node Node[nmax];
int sum[nmax], num[nmax];
void update(int i, int val, int n) {
while (i <= n) {
sum[i] += val;
i += lowbit(i);
}
}
int getSum(int i) {
int res;
res = 0;
while (i > 0) {
res += sum[i];
i -= lowbit(i);
}
return res;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int t, n, temp, i, j, k, res;
scanf("%d", &t);
for (i = 1; i <= t; i++) {
scanf("%d", &n);
for (j = 0; j < n; j++) {
scanf("%d", &Node[j].val);
Node[j].id = j;
}
sort(Node, Node + n);
memset(sum, 0, sizeof(sum));
num[Node[0].id] = 1, k = 1, temp = Node[0].val;
for (j = 1; j < n; j++) {
if (temp != Node[j].val) {
temp = Node[j].val;
num[Node[j].id] = ++k;
} else {
num[Node[j].id] = k;
}
}
for (j = n - 1, res = 0; j >= 0; j--) {
update(num[j], 1, n + 1);
res += getSum(num[j] - 1);
}
printf("Scenario #%d:\n%d\n", i, res);
if (i < t) {
printf("\n");
}
}
return 0;
}
pku 2299
/*
* poj2299.c
*
* Created on: 2011-9-29
* Author: bjfuwangzhu
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define nmax 500001
#define LL long long
#define lowbit(x) x&(-x)
typedef struct node {
int val, id;
} node;
node Node[nmax];
int n;
int sum[nmax];
void update(int i, int val) {
while (i <= n) {
sum[i] += val;
i += lowbit(i);
}
}
int getSum(int i) {
LL res;
res = 0;
while (i > 0) {
res += sum[i];
i -= lowbit(i);
}
return res;
}
int cmp(const void *a, const void *b) {
node n = *(node *) a;
node m = *(node *) b;
return n.val - m.val;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int i;
LL res;
while (~scanf("%d", &n) && n) {
for (i = 0; i < n; i++) {
scanf("%d", &Node[i].val);
Node[i].id = i + 1;
}
qsort(Node, n, sizeof(Node[0]), cmp);
memset(sum, 0, sizeof(sum));
for (i = 0, res = 0; i < n; i++) {
res += i - getSum(Node[i].id);
update(Node[i].id, 1);
}
printf("%I64d\n", res);
}
return 0;
}
sgu 180
归并排序
/*
* sgu180.c
*
* Created on: 2011-9-29
* Author: bjfuwangzhu
*/
#include<stdio.h>
#include<string.h>
#define nmax 65538
#define LL long long
int num[nmax], temp[nmax];
LL res;
int n;
void merge(int left, int mid, int right) {
int i, j, k;
i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (num[j] < num[i]) {
temp[k++] = num[j++];
res += (mid - i + 1);
} else {
temp[k++] = num[i++];
}
}
while (i <= mid) {
temp[k++] = num[i++];
}
while (j <= right) {
temp[k++] = num[j++];
}
for (i = 0; i < k; i++) {
num[left++] = temp[i];
}
}
void mergeSort(int left, int right) {
int mid;
if (left < right) {
mid = (left + right) >> 1;
mergeSort(left, mid);
mergeSort(mid + 1, right);
merge(left, mid, right);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int i;
while (~scanf("%d", &n)) {
for (i = 0; i < n; i++) {
scanf("%d", num + i);
}
res = 0;
mergeSort(0, n - 1);
printf("%I64d\n", res);
}
return 0;
}
树状数组C++版AC
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
#define nmax 65550
#define LL long long
#define lowbit(x) x&(-x)
typedef struct node {
int val, id;
bool operator<(const node &m) const {
return val < m.val;
}
} node;
node Node[nmax];
int sum[nmax], num[nmax];
void update(int i, int val, int n) {
while (i <= n) {
sum[i] += val;
i += lowbit(i);
}
}
int getSum(int i) {
int res;
res = 0;
while (i > 0) {
res += sum[i];
i -= lowbit(i);
}
return res;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int i, temp, k, n;
LL res;
while (~scanf("%d", &n)) {
for (i = 0; i < n; i++) {
scanf("%d", &Node[i].val);
Node[i].id = i;
}
sort(Node, Node + n);
memset(sum, 0, sizeof(sum));
for (i = 0, temp = -1, k = 0; i < n; i++) {
if (temp != Node[i].val) {
num[Node[i].id] = ++k;
temp = Node[i].val;
} else {
num[Node[i].id] = k;
}
}
for (i = 0, res = 0; i < n; i++) {
res += i - getSum(num[i]);
update(num[i], 1, n + 1);
}
printf("%I64d\n", res);
}
return 0;
}
树状数组C版超时
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define nmax 65550
#define LL long long
#define lowbit(x) x&(-x)
typedef struct node {
int val, id;
} node;
node Node[nmax];
int sum[nmax], num[nmax];
void update(int i, int val, int n) {
while (i <= n) {
sum[i] += val;
i += lowbit(i);
}
}
int getSum(int i) {
LL res;
res = 0;
while (i > 0) {
res += sum[i];
i -= lowbit(i);
}
return res;
}
int cmp(const void *a, const void *b) {
node n = *(node *) a;
node m = *(node *) b;
return n.val - m.val;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int i, temp, k, n;
LL res;
while (~scanf("%d", &n)) {
for (i = 0; i < n; i++) {
scanf("%d", &Node[i].val);
Node[i].id = i;
}
qsort(Node, n, sizeof(Node[0]), cmp);
memset(sum, 0, sizeof(sum));
for (i = 0, temp = -1, k = 0; i < n; i++) {
if (temp != Node[i].val) {
num[Node[i].id] = ++k;
temp = Node[i].val;
} else {
num[Node[i].id] = k;
}
}
for (i = n - 1, res = 0; i >= 0; i--) {
update(num[i], 1, n + 1);
res += getSum(num[i] - 1);
}
printf("%I64d\n", res);
}
return 0;
}
请路过的大牛指导，为什么使用C过不了，C++ 就过了，仅仅是排序换了一个（从qsort到sort），就可以了，不懂为什么？