首页 > 代码库 > BestCoder3 1002 BestCoder Sequence(hdu 4908) 解题报告
BestCoder3 1002 BestCoder Sequence(hdu 4908) 解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4908
题目意思：给出 一个从1~N 的排列你和指定这个排列中的一个中位数m，从这个排列中找出长度为奇数，中位数是m的子序列有多少个。
我的做法被discuss 中的测试数据一下子就否定了。
这个是别人的做法，暂时留下来，有些地方还没真正弄懂，应该是缺了部分的知识没有学到。。。
留着先：
（1）http://blog.csdn.net/hcbbt/article/details/38377815
（2） 思路：找出m的位置sign，然后向前找比m小，cou++，的index[]在相应的位置加一（等向m后面找的时候发现比m大的元素，构成了一个BestCoder Sequence，直接就sum+=index[]），比m大，cou--，也在的index[]在相应的位置加一（这样就把m前面比m大的数 也加入到准备数组index中，当m后面有比m大的时候sum+=index[],就把m前面比m大的元素也算上了，也构成了一个BestCoder Sequence）
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 40010; 8 int a[maxn], h[maxn]; 9 10 int main()11 {12 int n, m;13 int mid = maxn/2;14 while (scanf("%d%d", &n, &m) != EOF)15 {16 int posm;17 for (int i = 1; i <= n; i++)18 {19 scanf("%d", &a[i]);20 if (a[i] == m)21 posm = i;22 }23 memset(h, 0, sizeof(h));24 int r = 0, l = 0;25 for (int i = posm; i <= n; i++)26 {27 if (a[i] > m)28 r++;29 else if (a[i] < m)30 r--;31 h[mid+r]++;32 }33 int cnt = 0;34 for (int i = posm; i >= 1; i--)35 {36 if (a[i] > m)37 l++;38 else if (a[i] < m)39 l--;40 cnt += h[mid-l];41 }42 printf("%d\n", cnt);43 }44 return 0;45 }
BestCoder3 1002 BestCoder Sequence(hdu 4908) 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。