首页 > 其他分享 >Codeforces Round 905 (Div. 2) D1. Dances (Easy version)(贪心+二分)

Codeforces Round 905 (Div. 2) D1. Dances (Easy version)(贪心+二分)

时间:2023-10-23 21:24:35浏览次数:47  
标签:905 int mid long Codeforces Dances version Easy

Codeforces Round 905 (Div. 2) D1. Dances (Easy version)

思路:

对于 \(a\),它的头默认为 \(1\),则 \(a_0\) = \(1\)

对于排完序的 \(a\) 与 \(b\) 数组

最优为从 \(a\) 的结尾删除,从 \(b\) 的开头删除

二分保留位数,删去 \(n-mid\) 位,即 \(a\) 从 \(0\) 开始,\(b\) 从 \(k\)(\(k=n-mid\))开始

\(a_0\) ~ $a_{mid-1} $ 与 \(b_k\) ~ $b_{n-1} $ 比较大小

若满足则右移\(mid\),更新最大的满足保留位数

则最小删去数为 \(n - l\)

#define int long long
#define ld long double

using namespace std;

const int N = 1e5 + 10;

int t, n, m;
int a[N],b[N];

bool check(int x)
{
    int k = n - x;
    for (int i = 0; i < x; i++)
    {
        if (a[i] >= b[i + k])
        {
            return false;
        }
    }
    return true;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i < n; i++)
    {
        cin >> a[i];
    }

    a[0] = 1;
    for (int i = 0; i < n; i++)cin >> b[i];

    sort(a, a + n);
    sort(b, b + n);

    
    int l = 0, r = n, mid=0;
    while (l<r)
    {
        mid = (l + r+1) >> 1;//mid为a保留mid位,即删去n-mid位
        if (check(mid))
        {
            l = mid;
        }
        else r = mid - 1;
    }
    cout << n - l << endl;
}

signed main()
{
    //t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}

标签:905,int,mid,long,Codeforces,Dances,version,Easy
From: https://www.cnblogs.com/ikunhuaji/p/17783507.html

相关文章

  • 「解题报告」Codeforces Round 905 (Div. 3)
    A.MorningYouaregivenafour-digitpincodeconsistingofdigitsfrom\(0\)to\(9\)thatneedstobeentered.Initially,thecursorpointstothedigit\(1\).Inonesecond,youcanperformexactlyoneofthefollowingtwoactions:Pressthecu......
  • Codeforces Round 905 (Div. 2) C. You Are So Beautiful(数据结构)
    CodeforcesRound905(Div.2)C.YouAreSoBeautiful定义:设数组abcd子数组定义:从原数组砍去前面若干元素,后边若干元素,剩余的数组。如:bc、ab子序列定义:从原数组删除若干元素,剩余元素拼凑一起,组成的数组。如:ac、bd思路:作为结果的连续子数组,如果他为[\(a_l\),……,\(a_......
  • Educational Codeforces Round 144(CF1796 D~E) 题解
    D.MaximumSubarray题目链接十分钟秒了一道*2000,非常爽,但是个人感觉确实非常简单。下面令\(b_i=a_{i}-x\),\(b_i'=a_i+x\)。因为\(k<=20\),因此考虑一个复杂度与\(k\)相关的做法。不妨dp:设\(f_{i,j,0/1}\)表示考虑了前\(i\)个数,对\(j\)个数加上了\(x\),第\(i\)......
  • Codeforces Round 905 (Div. 2)
    目录写在前面ABCD1/D2E写在最后写在前面比赛地址:https://codeforces.com/contest/1884oonp这场div2怎么才2k5人打啊我草里面还不知道多少大神的小号,呃呃打了1k3掉了75分也是牛逼A考虑如何拼出一个长度为\(n-k\)的回文串,先一对一对地拼,再看需不需要再顶上去一个......
  • Codeforces Round 905 - div.3(A B C D E)
    目录CodeforcesRound905(Div.3)A.MorningB.ChemistryC.RaspberriesCodeforcesRound905(Div.3)A.Morning模拟光标移动即可voidsolve(){ stringss; cin>>ss; charch='1'; intans=0; for(autoc:ss){ if(c!=ch){ intx=c,y=c......
  • Codeforces Round 904 (Div. 2)
    目录写在前面ABCD写在最后写在前面比赛地址:https://codeforces.com/contest/1884捏吗我不会容斥,我是飞舞。A\(k\le10\),于是直接枚举\(x\simx+20\)检查即可。///*By:Luckyblock*/#include<bits/stdc++.h>#defineLLlonglong//=================================......
  • Codeforces Round 855 (Div. 3) C. Powering the Hero
    有\(n\)张卡的卡堆,你可以自顶向下抽卡。装备卡显示数值为\(a_i(a_i>0)\),英雄卡显示数值为\(a_i=0\)。如果是装备卡,你可以将卡抽出放在装备堆。如果是英雄卡,你可以将装备堆顶端的一张数值为\(x\)的装备卡装备给英雄,英雄数值\(+x\)。无论是否装备,都加入英雄堆。询问......
  • Codeforces Round 857 (Div. 2) B. Settlement of Guinea Pigs
    你非常喜欢豚鼠。每个笼子可以住两只豚鼠,且你不想把每个笼子放入不同性别的豚鼠。豚鼠只有两种性别。假设你买到豚鼠时并不知道性别,只有医生能够分辨。接下来的\(n\)天方案中,若第\(i\)天为\(1\),你买入一只豚鼠;若为\(2\),你请医生分辨你的豚鼠性别。给出方案,你最少需要准......
  • Educational Codeforces Round 145 (Rated for Div. 2) B. Points on Plane
    给一个二维平面,你需要在上面放\(n\)个芯片。将一个芯片放在\((x,y)\)的代价为\(|x|+|y|\)。放\(n\)个代价的代价为,所有芯片中耗费的最大代价。并且你需要保证任意两个芯片之间的距离严格\(>1\)。现在给出\(n\)给芯片,询问放\(n\)个芯片的最小代价。一:不难想到......
  • Educational Codeforces Round 149 (Rated for Div. 2)
    这场D被切穿了。A题答案为x或者x-11B题答案就是最长的连续一段的长度+1证明的话大概可以将它看成是几段连续上升和下降的段,然后在峰谷、峰顶分别填上最小、最大,剩下的就依次递增或递减就行。C题将一段连续的0/1视作一个块,那么我们最小化这个块的数量就行。D题如果猜到......