• [NOIP2016 提高组] 蚯蚓


    题目链接

      题目很长,题意如下:一开始有n个值,,有m次操作,每次操作选择一个最大的值x,将它分解成两个数,分别为\left \lfloor u \times x / v \right \rfloor,以及x - \left \lfloor u \times x / v \right \rfloor,然后,经过这个操作之后,对除了这两个数以外的其他数字进行 +q 操作。最后两行输出,第一行输出,是每次操作执行之前,我们找到的那个最大的值是多少;第二行输出,是我们执行完m次操作,现在这n+m个值都各自变成了几?

      由于输入的量加上操作的量很大,所以我们不能使用带有O(log_2)复杂度的大根堆来解决这个问题,这无疑是加大了我们这道问题的难度!

      那么,这暗示着我们需要寻找其中的“线性关系”了。

      我们会发现,我们取出来的值一定是排除“增量q”情况下的递减的。但,我们再想一下,同样经过T次“增量q”,如果先分解的两个,是不是后期分得的“增量q”会更多呢(因为分解成了两个,相当于每个都享受到了这样的优惠,但是没分解的,现在是两个共享同一个“增量q”),先分解的在随着时间的推移反而会越来越有优势。

      所以,我们不妨维护三个队列:

    队列1:原本的值,按照从大到小排序

    队列2:分解之后,值偏大的那个,那么值越大的一定就先分解了,享受“增量q”福利肯定也更早;

    队列3:分解之后,值偏小的那个,作用同上。

      那么,又如何维护“增量q”呢,实际上,我们只需要再多统计一个信息就可以了,就是这个值是第几轮生成的,用当前轮次减去生成的轮次,不就得到了它需要被增加多少次了呢。

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int maxn = 1e5 + 7;
    5. int n, m, q, t;
    6. ll u, v;
    7. ll a[maxn];
    8. struct node {
    9. ll val, id;
    10. node(ll a = 0, ll b = 0):val(a), id(b) {}
    11. friend bool operator < (node e1, node e2) {
    12. return e1.val - e1.id * q < e2.val - e2.id * q;
    13. }
    14. ll F(ll i) { return val + (i - id) * q; }
    15. };
    16. struct Heap {
    17. queue Q[3];
    18. void clear() {
    19. for(int i = 0; i < 3; i ++) while(!Q[i].empty()) Q[i].pop();
    20. }
    21. bool empty() { return Q[0].empty() && Q[1].empty() && Q[2].empty(); }
    22. node Top() {
    23. node ans;
    24. int qid = -1;
    25. for(int i = 0; i < 3; i ++) {
    26. if(Q[i].empty()) continue;
    27. if(~qid) {
    28. if(Q[qid].front() < Q[i].front()) qid = i;
    29. }
    30. else qid = i;
    31. }
    32. ans = Q[qid].front();
    33. Q[qid].pop();
    34. return ans;
    35. }
    36. } que;
    37. int main() {
    38. scanf("%d%d%d%lld%lld%d", &n, &m, &q, &u, &v, &t);
    39. for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
    40. sort(a + 1, a + n + 1, greater() );
    41. que.clear();
    42. for(int i = 1; i <= n; i ++) que.Q[0].push(node(a[i], 0));
    43. int tot = m / t;
    44. if(!tot) printf("\n");
    45. for(int i = 0; i < m; i ++) {
    46. node now = que.Top();
    47. if((i + 1) % t == 0) {
    48. tot --;
    49. printf("%lld%c", now.F(i), tot ? ' ' : '\n');
    50. }
    51. ll x = now.F(i) * u / v, y = now.F(i) - x;
    52. if(x < y) swap(x, y);
    53. que.Q[1].push(node(x, i + 1));
    54. que.Q[2].push(node(y, i + 1));
    55. }
    56. tot = (n + m) / t;
    57. if(!tot) printf("\n");
    58. for(int i = 1; i <= n + m; i ++) {
    59. node now = que.Top();
    60. if(i % t == 0) {
    61. tot --;
    62. printf("%lld%c", now.F(m), tot ? ' ' : '\n');
    63. }
    64. }
    65. return 0;
    66. }

  • 相关阅读:
    Kotlin(十一)Kotlin中的Object关键字
    0 基础 Java 自学之路(3)
    减轻压力保护脊椎,上学路上更轻松,Deuter多特护脊减负双肩背包体验
    从实体经济和数字经济融合展开,思考商业模式的变化
    高项_第八章项目质量管理
    基于JAVA双峰县在线房屋租售网站计算机毕业设计源码+数据库+lw文档+系统+部署
    laravel - 查询构建器2
    吃透Redis(三):数据结构篇-skiplist、quicklist、listpack
    枚举(enum)
    Vue学习之--------深入理解Vuex、原理详解、实战应用(2022/9/1)
  • 原文地址:https://blog.csdn.net/qq_41730082/article/details/133099802