微策略面试题---关于权重
我的思路：
给定一个N个整数元素的数组，元素分别为A1, A2, A3....AN，每个元素分别对应一个权重W1（小于1的float）, W2,W3....WN, 其和为1.找出其中一个元素Ak,使所有小于Ak的元素的权重之和小于1/2，所有大于Ak的元素的权重之和>=1/2.


（1）将该数组按元素的值得大小升序排列；

（2）

sum = w[1];//小于Ak的元素的权重之和

for(k=2;k<=n;k++)

{

if(sum < 1/2 && sum + w[k] <= 1/2)

return A[k];

sum += w[k];

}

请问我这样的做法有没有什么问题？有没有更好的方法？

[解决办法]

探讨

其实求出中间元素的前一个元素的值就可以了

C/C++ code

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
int a[] = {9, 1, 5, 4, 2, 3, 7, 4, 2, 6, 8, 3, 7};

int *result = nt……

[解决办法]
楼主的思路是对的，只是描述的时候有点问题，首先将该数组按元素的值的大小升序排列，同样的那个权值数组也要对应的进行排序，因为原先的那个数组的下标和权值数组的下标是相对应的，如果权值数组不跟着变化的，那么就无法知道某一个数的权值是多少了，就无法对应起来了。。
另外就是，那个sum有可能会大于1/2，这个时候就直接返回-1，表示没有找到就可以了。。
sum = w[1];//小于Ak的元素的权重之和
for(k=2;k<=n;k++)
{
if(sum>1/2)
return -1;
if(sum < 1/2 && sum + w[k] <= 1/2) //sum < 1/2 保证使所有小于Ak的元素的权重之和小于1/2
//sum + w[k] <= 1/2，使得小于等于Ak的元素权重之和小于等于1/2，也就是所有大于Ak的元素的权重之和>=1/2.
return A[k];
sum += w[k];
}