首页 > 其他分享 >Greedy

Greedy

时间:2023-09-23 17:46:38浏览次数:33  
标签:int scanf Greedy ans include define

P4090 [USACO17DEC] Greedy Gift Takers P

我们可以发现构成循环的一定是前面的任意一个前缀。

考虑二分答案。

然后,我们对于这个分界点 \(mid\),我们需要知道他是否能被移动到开头。

贪心的考虑,我们优先让 \(c\) 小的移动到后面,这样大的更容易移动到后面。

可以使用计数排序,时间复杂度 \(O(n\log n)\)。

#include<cstdio>
#include<queue>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while

const int N=300010;
int n;
typedef long long ll;
ll ans;
priority_queue<int,vector<int>,greater<int>>q;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    scanf("%d",&n);
    E(i, n){
        int x;
        scanf("%d",&x);
        if(!q.empty()&&x>q.top()){
            ans+=(x-q.top());
            q.pop();
            q.push(x);
        }
        q.push(x);
    }
    printf("%lld",ans);
    return 0;
}

标签:int,scanf,Greedy,ans,include,define
From: https://www.cnblogs.com/wscqwq/p/17724773.html

相关文章

  • 2023.9.13 greedy and DS
    CF1439C考虑修改操作,由于序列是单调的,所以只需要线段树二分出修改的区间即可。考虑查询,一定是若干个连续段,设一开始是\(y\),这个连续段结束后,\(y\)至少减去一半,所以连续段个数是\(\log\)级别。在线段树上遍历即可。......
  • CF1132G Greedy Subsequences
    简单题。\(i\)向\(i\)后第一个\(j\),\(a_j\)比\(a_i\)大的点连边,不难发现最后形成了一棵森林,并且一个点的父亲\(\text{fa}_i>i\)。题目变成了取\([l,r]\)中的点为起点,向祖先方向走去并且终点编号\(\ler\)的最长链长度。考虑离线,维护从每个点开始的最长链长度\(f_i......
  • AtCoder Beginner Contest 212 F Greedy Takahashi
    洛谷传送门AtCoder传送门考虑每条边,因为是静态的,所以可以预处理出\(f_{i,j},g_{i,j}\)表示从第\(i\)条边,往后跳\(2^j\)条边,跳到边的编号和目前的时间(如果不存在就当作跳到第\(0\)条边)。直接倍增处理即可。询问就是找到从\(u\)开始的出边,能跳尽量跳。注意一些细节......
  • 【多臂赌机】基于时变egreedy策略结合强化学习求解多臂赌机问题附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • Codeforces Round #225 (Div. 2) C. Milking cows Greedy
    Iahubhelpshisgrandfatheratthefarm.Todayhemustmilkthecows.Therearencowssittinginarow,numberedfrom1tonfromlefttoright.Eachcowiseitherfacingtotheleftorfacingtotheright.WhenIahubmilksacow,allthecowsthatseet......
  • Value targets in off-policy AlphaZero: a new greedy backup
    发表时间:2021文章要点:这篇文章给AlphaZero设计了一个新的valuetargets,AlphaZerowithgreedybackups(A0GB)。AlphaZero的树里面有探索,而value又是所有结果的平均,所以并不准确。而选动作也是依概率选的,但真正测试的时候是选的访问次数最多的动作,所以这个方法是off-policy,也会......
  • CF10E Greedy Change 题解
    一个非常离谱的题。首先有结论,如果有\(w\)使贪心不为最优解,那么比\(w\)小的第一个\(a_i\),用贪心法求面值为\(a_i-1\),除了最后选的一个数\(a_j\)会比原方法多选一......
  • CTC的训练与推理之Greedy Decoder, Beam Search,CTC Loss, RNNT Loss
    模型流程:t时刻输入x(t),t-1时刻输出y`(t-1),t时刻的输出y`(t)为:由x(t)和y`(t-1)作为输入得到的预测值训练:采用TeacherForcing的策略,在t时刻,并不是使用上一时刻的预测值y`(......
  • greedy
    621.任务调度器classSolution:defleastInterval(self,tasks:List[str],n:int)->int:#1.假设任务间隔为n,最短完成任务时间就是任务总数......
  • PAT (Top Level) Practise 1012 Greedy Snake (35)
    1012.GreedySnake(35)时间限制1000ms内存限制65536kB代码长度限制8000B判题程序Stand......