这个题目尝试了很多种方法都过不去, 上网查了一下网友们的的思路, 竟然和逆序对数有关系!!
题目大意:
有 n 个士兵, 他们都有各自的分数, 有一项任务需要完成, 为了能够确保合作更默契, 他们的分数要差不多, 所以有一个水平控制即平均数, 所选的一组士兵的平均成绩必须大于该平均数
问一共能选出多少组士兵能够完成该项任务?
思路:
求逆序对数归并排序可以用来求逆序对数, 这个没毛病
代码如下:
- #include<iostream>
- #include<cstring>
- using namespace std;
- void combine_sortd_list(int* to, int* sub1, int sz1, int* sub2, int sz2);
- void merge_sort(int* lst, int sz);
- const int MAX = 1e5 + 5;
- int arr[MAX];
- long long int ans;
- int main()
- {
- int Group, N, A;
- cin >> Group;
- while (Group--)
- {
- memset(arr, 0, sizeof arr);
- cin >> N >> A;
- for (int j, i = N-1; i >=0; --i)
- {
- cin >> j;
- arr[i] = j - A + arr[i + 1];
- }
- ans = 0;
- merge_sort(arr, N + 1); // 归并求逆序数
- cout << ans << endl;
- }
- }
- void merge_sort(int* lst, int sz)
- {
- static int tmp[MAX];
- if (sz <= 1)return;
- int* l = lst;
- int lsz = (sz + 1) / 2;
- int* r = l + lsz;
- int rsz = sz / 2;
- merge_sort(l, lsz);
- merge_sort(r, rsz);
- combine_sortd_list(tmp, l, lsz, r, rsz);
- for (int i = 0; i < sz; ++i)lst[i] = tmp[i];
- }
- void combine_sortd_list(int*to, int* sub1, int sz1, int* sub2, int sz2)
- {
- int i = 0, j = 0, k = 0;
- while (i < sz1&&j < sz2)
- if (sub1[i] <= sub2[j])to[k++] = sub1[i++];
- else
- {
- ans += sz1 - i;
- to[k++] = sub2[j++];
- }
- while (i < sz1)to[k++] = sub1[i++];
- while (j < sz2)to[k++] = sub2[j++];
- }
由公式推导解析题目意图: http://blog.csdn.net/scorpiocj/article/details/6227528
来源: http://www.bubuko.com/infodetail-2503806.html