P1631-序列合并

刺骨的言语ヽ痛彻心扉 2023-06-01 08:55 6阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     4 #define INF 0x3f3f3f3f
     5 #define MOD 1000000007
     6 #define pb push_back
     7 #define maxn 100003 
     8 typedef long long ll;
     9 using namespace std;
    10 inline ll read()
    11 {
    12     ll ans = 0;
    13     char ch = getchar(), last = ' ';
    14     while(!isdigit(ch)) last = ch, ch = getchar();
    15     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    16     if(last == '-') ans = -ans;
    17     return ans;
    18 }
    19 inline void write(ll x)
    20 {
    21     if(x < 0) x = -x, putchar('-');
    22     if(x >= 10) write(x / 10);
    23     putchar(x % 10 + '0');
    24 }
    25 int N;
    26 struct P
    27 {
    28     int k;
    29     int val;
    30 };
    31 struct cmp
    32 {
    33     bool operator () (P a,P b)
    34     {
    35         return a.val > b.val;
    36     }
    37 };
    38 priority_queue<P,vector<P>,cmp> pq;
    39 int a[maxn];
    40 int b[maxn];
    41 int k[maxn];
    42 int main()
    43 {
    44     N = read();
    45     _for(i,1,N+1)
    46         a[i] = read();
    47     _for(i,1,N+1)
    48         b[i] = read();
    49     
    50     _for(i,1,N+1)
    51     {
    52         pq.push({i,a[i]+b[1]});
    53         k[i] = 1;
    54     }
    55     
    56     _for(i,1,N+1)
    57     {
    58         P ans = pq.top();
    59         pq.pop();
    60         printf("%d ",ans.val);
    61         k[ans.k] ++;
    62         pq.push({ans.k,a[ans.k]+b[k[ans.k]]});
    63     }
    64     return 0;
    65 }

转载于:https://www.cnblogs.com/Asurudo/p/11564213.html

发表评论取消回复

表情：

评论列表（有 0 条评论，6人围观）

还没有评论，来说两句吧...

相关阅读

相关 oj 合并有序序列

合并有序序列 Time Limit: 1000/1000MS (C++/Others) Memory Limit: 65536/65536KB (C++/Others)

灰太狼/ 2023年10月05日 14:24/ 0 赞/ 30 阅读

相关 P1631-序列合并

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

刺骨的言语ヽ痛彻心扉/ 2023年06月01日 08:55/ 0 赞/ 6 阅读

相关 P1880-[NOI1995]石子合并

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

蔚落/ 2023年06月01日 08:51/ 0 赞/ 39 阅读

相关 Vijos P1097合并果子

P1097合并果子 [Wrong Answer][] 标签： [NOIP提高组2004][NOIP_2004] \[显示标签\] 描述在一个果园里，多多已经将所有

缺乏、安全感/ 2022年08月20日 13:17/ 0 赞/ 192 阅读

相关 poj-1631Bridging signals(LIS)

Bridging signals <table> <tbody> <tr> <td><strong>Time Limit:</strong> 10

逃离我推掉我的手/ 2022年08月10日 00:44/ 0 赞/ 133 阅读

相关【p1880】石子合并

[https://www.luogu.org/problem/show?pid=1880][https_www.luogu.org_problem_show_pid_1880]

忘是亡心i/ 2022年06月06日 01:55/ 0 赞/ 164 阅读

相关洛谷P1090 合并果子

题目描述在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗

你的名字/ 2022年05月31日 10:50/ 0 赞/ 206 阅读

相关 poj 1631Bridging signals Dp（最长递增子序列）

Bridging signals <table> <tbody> <tr> <td><strong>Time Limit:</strong> 10

古城微笑少年丶/ 2022年04月01日 08:54/ 0 赞/ 175 阅读

相关 P1090 合并果子——————multiset

[P1090 合并果子][P1090] 题目描述在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

朴灿烈づ我的快乐病毒、/ 2022年03月31日 06:52/ 0 赞/ 235 阅读

相关 LOJ P10147 石子合并题解

Analysis 区间dp+前缀和 include<iostream> include<cstdio> include<cstring>

向右看齐/ 2021年10月19日 19:16/ 0 赞/ 284 阅读