首页 > 其他分享 >YL 模拟赛总结 15

YL 模拟赛总结 15

时间:2024-03-02 17:25:57浏览次数:25  
标签:node sort 15 YL int bool 堆中 模拟

Problem


T1

感觉是最难的。

考虑贪心。

首先对牛的按左端点进行排序,然后对于每只鸡去考虑匹配哪头牛。

具体地,开一个小根堆,然后对于每只鸡 \(t_i\),将 \(a_i \le t_i\) 的牛放入堆中,此时堆中存放的是候选的牛。

然后对于堆中的牛,将 \(b_i<t_i\) 的牛弹出。

此时堆中的牛均是合法的,累加堆的大小即可。

#include<bits/stdc++.h>
using namespace std;

int c,n,ans;
int t[20031];
struct node{
    int x,y;
    friend bool operator < (node a,node b){
        return a.y>b.y;
    }  
}a[20031];
priority_queue<node> pq;
bool cmp(node a,node b){
    return a.x<b.x;
}

int main(){
    cin>>c>>n;
    for(int i=1;i<=c;i++) cin>>t[i];
    for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
    sort(t+1,t+c+1),sort(a+1,a+n+1,cmp);
    for(int i=1,now=1;i<=c;i++){
        while(now<=n&&a[now].x<=t[i]) pq.push(a[now++]);
        while(!pq.empty()&&pq.top().y<t[i]) pq.pop();
        if(!pq.empty()) ans++,pq.pop();
    }
    cout<<ans;
    return 0;
}

T2

略。

T3

略。

T4

略。

标签:node,sort,15,YL,int,bool,堆中,模拟
From: https://www.cnblogs.com/XOF-0-0/p/18048909

相关文章

  • YL 模拟赛总结 14
    Problem省流:三道题写了tjT1见tj。T2见tj。T3见tj。T4二分求出左右端点即可。#include<bits/stdc++.h>usingnamespacestd;intn,q;intp[200031];intmain(){//freopen("haybales.in","r",stdin);//freopen("haybales.out",&quo......
  • YL 模拟赛总结 13
    ProblemT1略。T2略。T3考虑对于每一头向北的牛,计算它能够挡住/被挡住几头向东的牛。一头向北的牛\(i\)能够被向东的牛\(j\)挡住的条件是:\(x_i<x_j\)且\(y_i<y_j\)(\(x_i,y_i\)分别表示牛\(i\)的\(x\)坐标与\(y\)坐标);\(l_j\)没有被更新(\(l_i\)表示第......
  • YL 模拟赛总结 12
    ProblemT1略。T2最理想的情况当然是奇偶交替,每个数单独成为一组。考虑不理想的情况:偶数个数\(>\)奇数个数,此时需要可以先奇偶交替,再将最后剩下的偶数单独分为一组,答案为奇数个数\(\times\2+1\)。奇数个数\(>\)偶数个数,此时再分出两种情况:若奇数个数\(-\)......
  • YL 模拟赛总结 10
    ProblemT1二分板子。对于\(c_i\)降序排序,然后二分\(h\)指数,在check中贪心地使用综述增加引用次数即可。T2通过观察可以发现,在一篇论文的贡献列表中,若某一位置出现了比它前面的名字的字典序更小的情况,则说明从这个位置开始,后面的人的资历一定\(\ge\)前面的人。根据......
  • YL 模拟赛总结 9
    ProblemT1我们考虑一种贪心策略:对于价格前\(n-1\)小的咖啡,我们求出一种最优方案使得按照此方案买完咖啡后钱数\(\ge20\)且最接近\(20\)。至于如何求出最优方案,进行一遍01背包即可。#include<bits/stdc++.h>usingnamespacestd;intn,k;inta[1031],dp[1031];i......
  • YL 模拟赛总结 6
    ProblemT1为了方便处理,我们令男生为\(1\),女生为\(-1\)。求一遍前缀和\(sum\),若存在两个下标\(l,r\)使得\(sum_l=sum_r\),则说明区间\([l+1,r]\)的和为\(0\),即男女人数相等。在这样的区间中取长度最大的即可。需要特殊处理\(sum_0\)。#include<bits/stdc++.h>#defi......
  • YL 模拟赛总结 7
    ProblemT1预处理出前\(10^4\)个格子需要填什么数,然后输出即可。具体地,我们记录\(e\)为当前层数,\(o\)为上一层的最后一个的位置,\(last\)为上一个填的格子的位置。我们知道,一个格子要么在一层的起点,要么在一层的中间,要么在一层的末尾。枚举\(1\sim5\)分别对这三种情......
  • YL 模拟赛总结 11
    ProblemT1略。T2略。T3结论题。令所有牛的最终饥饿值为\(x\),则分别对于每一头牛进行考虑:对于第一头牛,它需要的最少玉米袋数为\(h_1-x\);对于第二头牛,它单独需要的最少玉米袋数为\(h_2-x\),而第一头牛已经用了\(h_1-x\)袋玉米,因此它需要的最少玉米袋数为\(h_2-x-......
  • CF15E
    参考(先看)这个题解最后的式子写错了,看最后(注意一下算层数要n/=2!)这里面关于\(ans\)的用法:为什么是\(2\timesans^2+8\timesans+10\)已经讲得很清楚了。主要补充一下怎么求\(ans\)的部分。如图,三个决策点的所在部分可以视作一个三角形+若干个斜着的梯形。经过这......
  • CF1915D Unnatural Language Processing 题解
    容易发现音节的划分不仅要求子串形如\(\texttt{CV}\)或\(\texttt{CVC}\),并且接下来的两个字符也必须是\(\texttt{CV}\),不然会导致无法划分下去。于是我们遍历字符串,找出所有满足上述条件的子串,记录需要输出\(\texttt{.}\)的位置即可。实现:intn;strings,ans,t="";cin>......