被表弟的高中竞赛题难住了

不知道小帅 发表于 2021-2-17 23:00
可以继续的。就是double类型也无所谓，可以把精度控制的，就是你二分的边界可以是double，然后写成这样， ...

明白了！感谢感谢！

pphuangyi 发表于 2021-2-18 00:25
明白了！感谢感谢！

没事。。刚刚打错了，应该是大于tol。不是小于。然后你如果想测验的话，可以用IDE来写一些test，因为这个题目的暴力解非常容易写，除了耗时长一点之外。你可以写一份暴力解，然后写一份这个解法，生成随机数据，看下这个解法和暴力解给的结果是否匹配，这样就可以知道写得对不对了。

不知道小帅 发表于 2021-2-16 20:29
这个题目我的想法是二分。二分的思路可以参考leetcode的378题，也就是我们猜一个数， ...

prefix sum用得漂亮！

有一个问题没有明确，就是数组是否是排好序的，题目里给的1，2，3是排好序的。

假设无序的状态，想法是用heap保存平均值和起始index，终止index，window的和。比如这样
{ave, {start, end, sum}}
每次从heap里pop出一个，分别在start-1和end+1尝试，重新放回heap中。循环K次的到结果。

没有做很多测试，只是大概写了个思路，不知道数据量大了以后还能不能满足条件
大概代码长这个样子：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <queue>
   
4. using namespace std;
   
5. 
   
6. vector<double> findKSmallestAve(vector<int>& input, int K)
   
7. {
   
8.     priority_queue<pair<double, vector<int>>, vector<pair<double, vector<int>>>, greater<pair<double, vector<int>>>> pq;
   
9.     vector<vector<bool>> visited(input.size(), vector<bool>(input.size()));
   
10.     for(int i=0;i<input.size(); ++i)
    
11.     {
    
12.         pq.push({input[i], {i,i,input[i]}});
    
13.         visited[i][i] = true;
    
14.     }
    
15.    
    
16.     vector<double> res;
    
17.     for(int i=0; i<K && !pq.empty(); ++i)
    
18.     {
    
19.         res.push_back(pq.top().first);
    
20.         int start = pq.top().second[0];
    
21.         int end = pq.top().second[1];
    
22.         int sum = pq.top().second[2];
    
23.         pq.pop();
    
24.         if(start>0 && !visited[start-1][end])
    
25.         {
    
26.             pq.push({ (double)(sum+input[start-1])/(end-start+2), {start-1, end, sum+input[start-1]}});
    
27.             visited[start-1][end]=true;
    
28.         }
    
29.         if(end<input.size()-1 && !visited[start][end+1])
    
30.         {
    
31.             pq.push({(double)(sum+input[end+1])/(end-start+2), {start, end+1, sum+input[end+1]}});
    
32.             visited[start][end+1]=true;
    
33.         }
    
34.     }
    
35.     return res;
    
36. }
    
37. 
    
38. int main()
    
39. {
    
40.     vector<int> input{2,1,3};
    
41.    for(auto i : findKSmallestAve(input, 6)) cout << i << ", ";
    
42.    
    
43.    return 0;
    
44. }

复制代码

[i][i][i]

顺便求个大米[/i][/i][/i][/i][/i][/i][/i]

glambertjay 发表于 2021-2-17 12:49
很合理！太厉害了！我的等级还远远不够竞赛题😭😭

话说楼主有没有这个题目的online judge啊？想写写试试。

不sort，试试用priority queue呢？

Vbloody 发表于 2021-2-17 02:00
我文科生……那天看了个初中数学题，也不能算竞赛题吧，我特么做不来………连题目都没看明白，气的我赶紧点 ...

确实 题目没看明白没事 奶茶得喝！

不知道小帅 发表于 2021-02-18 11:25:27
话说楼主有没有这个题目的online judge啊？想写写试试。

没，得要有他们内部的账号才能测

glambertjay 发表于 2021-2-19 07:38
没，得要有他们内部的账号才能测

这样子啊，那他写了吗？这种做法过不过得了啊？

不知道小帅 发表于 2021-02-18 16:12:06
这样子啊，那他写了吗？这种做法过不过得了啊？

现在过了contest时间不让跑了，不过我自己拿极限情况跑下来没超time limit