牛客多校赛题解（六）

1.Intervals on the Ring

题目链接：I-Intervals on the Ring_2021牛客暑期多校训练营6 (nowcoder.com)

题目大意

有一个环，环上有一堆数字，现在给定了一个m个不重叠的区间，现在要求k个区间，使得k个区间的交集与m个区间的并集相同

解题思路

本题由于给的是环形数组，因此可考虑将数字由 1 ~ n 按类时钟方法排列为一圈，而所给的区间即为由 l 按顺时针方向到 r 所覆盖的区间。

不难发现，在该环形数组中，不属于 m 个区间的并集 的集合的个数即为 k 的最小值，而 k 个集合由 m 中每一个集合的 l 到下一个（顺时针）集合的 r 组成

参考:Intervals on the Ring（2021牛客多校第六场I）_国家一级划水运动员的博客-CSDN博客

ACCode

/*
 * @Author: NorthCityChen
 * @LastEditTime: 2021-08-05 20:23:47
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) NorthCityChen All rights reserved.
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4;
struct node
{
    int l;
    int r;
} a[N];
bool cmp(node x, node y)
{
    return x.l < y.l;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        int l, r;
        for (int i = 0; i < m; i++)
        {
            cin >> a[i].l >> a[i].r;
        }
        sort(a, a + m, cmp);
        cout << m << endl;
        cout << a[0].l << ' ' << a[m - 1].r << endl;
        for (int i = 1; i < m; i++)
        {
            cout << a[i].l << " " << a[i - 1].r << endl;
        }
    }
    return 0;
}

2.Delete Edges

题目链接：C-Delete Edges_2021牛客暑期多校训练营6 (nowcoder.com)

题目大意

给定一个有 n 个点的完全无向图，每次在其中选出三个点，若这每两个点间的边都存在，则删去这三条边。可操作 m 次，直到该图中剩下的边的个数小于 n 为止。（ 操作次数不需要最小 ）

解题思路

这道题虽然表面上是图论，但考察的内容是如何避免出现重复的两两组合数，因为当删去某个三角形后，其中的任意两点将不能一起再出现在新的三角形内。而需要进行的最小操作次数也可通过数学公式推出：在该完全无向图中共有 [ n ( n - 1 ) ] / 2 条边，每次操作将减去 3 条边，因此操作次数 m = ( n ( n - 1 ) / 2.0 - n ) / 3.0 + 1 ;

由于本题需要保证两两间的组合不重复出现，因此可以在保证输出的三个点中 第三点 > 第二点 > 第一点 的前提下进行暴力枚举即可

原文参考：Delete Edges（2021牛客多校第六场C）_国家一级划水运动员的博客-CSDN博客

ACCode

/*
 * @Author: NorthCityChen
 * @LastEditTime: 2021-08-05 20:23:47
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) NorthCityChen All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,z;
int main(){
    int i,j;
    cin>>n;
    int k;
    m=(n*(n-1)/2.0-n)/3.0+1;
    cout<<m<<endl;
    for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++){
        k=n-i-j;
        if(k<=0) k+=n;
        if(k>j) printf("%d %d %d\n",i,j,k);
    }
    return 0;
}

3.Hamburger Steak

题目链接：F-Hamburger Steak_2021牛客暑期多校训练营6 (nowcoder.com)

题目大意

有m个锅要煎n块牛肉饼，每个锅只能同时煎一块饼，每个饼只能同时被一个锅煎，但是一块饼可以在不同的时间被两个锅煎，现在问煎这些饼最小需要多少时间

解题思路

对于这些肉饼来说，煎制的最少时间为max(最大肉饼花费, 肉饼总花费/锅的总数)，因此，为满足最小这个条件，应当将这些肉饼排序以后，一次放入煎锅开始煎，使每个锅都能尽量完美的利用所有的时间即可

ACCode

/*
 * @Author: NorthCityChen
 * @LastEditTime: 2021-08-05 22:23:37
 * @Description: 
 * @Website: https://grimoire.cn
 * Copyright (c) NorthCityChen All rights reserved.
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
typedef pair<ll, ll> pii;
pii a[N];
ll t[N];
ll p[N];

int main()
{
    ll n, m, pan1 = 1, pan2, ta1, ta2, tb1, tb2, sign; //pan:前pan-1的盘子已满不用考虑
    memset(p, 0, sizeof(p));
    ll sum = 0;
    cin >> n >> m;
    for (ll i = 1; i <= n; i++)
    {
        cin >> t[i];
        sum += t[i];
        a[i] = pii(t[i], i);
    }

    ll ave = sum / m;
    if (sum % m != 0)
        ave++;

    sort(a + 1, a + n + 1);
    if (a[n].first > ave)
        ave = a[n].first;

    for (ll i = 1; i <= n; i++)
    {
        if (t[i] + p[pan1] > ave)
        {
            ta1 = p[pan1], ta2 = ave;
            cout << '2' << ' ';
            t[i] = t[i] - ave + p[pan1];
            sign = pan1;
            pan1++;
            pan2 = pan1;
            while (p[pan2] + t[i] > ave || p[pan2] + t[i] > ta1)
                pan2++;
            tb1 = p[pan2];
            p[pan2] += t[i];
            tb2 = p[pan2];
            cout << pan2 << ' ' << tb1 << ' ' << tb2 << ' ' << sign << ' ' << ta1 << ' ' << ta2 << endl;
        }
        else
        {
            cout << '1' << ' ' << pan1 << ' ' << p[pan1] << ' ';
            p[pan1] += t[i];
            cout << p[pan1] << endl;
        }
        if (p[pan1] == ave)
            pan1++;
    }
    return 0;
}