7、牛客练习—-牛客周赛Round35

A：小红的字符串切割

链接

题目描述

小红拿到了一个长度为偶数的字符串，请你将其切割成长度相等的两部分并输出。

输入描述:

1
一个长度为偶数的字符串。长度不超过10510^5105

输出描述:

1
输出两行，分别代表切割后的字符串。

​ 示例1

输入

复制

1
arcaea

输出

复制

1
2
arc
aea

代码

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int len = s.length();
    cout << s.substr(0, len / 2) << '\n' << s.substr(len / 2,len);
    
    return 0;
}

B：小红的数组分配

链接

题目描述

小红拿到了一个长度为2∗n的数组，她希望你将其中所有元素分配到两个长度相等的数组a和b，满足对于1≤i≤n有ai=bi。你能帮帮她吗？

输入描述:

1
2
3
4
第一行输入一个正整数n。
第二行输入2∗n个元素xi，代表小红拿到的数组。
1≤n≤105
1≤xi≤109

输出描述:

1
2
如果无解，请输出 -1。
否则第一行输出n个正整数ai，代表aaa数组；第二行输出n个正整数bi，代表b数组。有多种分配方案时，输出任意合法的均可。

示例1

输入

复制

1
2
2
1 4 4 1

输出

复制

1
2
4 1
4 1

代码一（使用map）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 1e5 + 10;
int a[N * 2];
unordered_map<int, int> b;
int n, res, k;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;    
    int m = n * 2;
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        b[x]++;
    }          
    for (auto k:b) {
        if (k.second % 2) {
            cout << -1;           
            return 0;
        }
    }
    
    for (auto k:b) {
        for (int i = 0; i < k.second / 2; i++) cout << k.first << " ";
    }
    cout << '\n';
    for (auto k:b) {
        for (int i = 0; i < k.second / 2; i++) cout << k.first << " ";
    }

    return 0;
}

代码二（数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N * 2];
int n;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;    
    int m = n * 2;
    for (int i = 1; i <= m; i++) cin >> a[i];
    sort(a + 1, a + m + 1);
    for (int i = 2; i <= m; i += 2) {
        if (a[i] != a[i - 1]) {
            cout << -1;
            return 0;
        } 
    }
    for (int i = 2; i <= m; i += 2) cout << a[i] << " ";
    cout << '\n';
    for (int i = 2; i <= m; i += 2) cout << a[i] << " ";

    return 0;
}

C：小红关鸡

链接

题目描述

​ img

​ 有n个鸡窝排成一排，第i个鸡窝在数轴上的坐标是xi，有一只小鸡会随机的在一个鸡窝中出现。小红准备在数轴上放置两个栅栏，如果小鸡出现在两个栅栏中间（包括端点），则将被小红关住。为了方便管理，两个栅栏之间的最大距离不能超过k。现在小红希望最大化成功“关鸡”的概率，请你帮小红求出这个概率。

输入描述:

1
2
3
4
5
第一行输入两个正整数n,k，代表鸡的数量和栅栏的最远距离。
第二行输入nnn个整数xi，代表每个鸡的位置。
1≤n≤105
1≤k≤109
−109≤xi≤109

输出描述:

1
一个浮点数，代表小红成功关鸡的概率。如果你的答案和标准答案的误差不超过10^−4，则认为你的答案正确。

示例1

输入

复制

1
2
5 5
2 3 -1 4 9

输出

复制

1
0.8

说明

1
小红将两个栅栏放置在 -1 和 4 这两个点，这样有 80% 的概率能成功关鸡。

代码一（二分）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
 
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL a[N];
LL n, k,res;
 
 
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        LL kk = a[i];
        LL l = 1, r = n;
        while (l < r) {
            LL mid = l + r + 1 >> 1;
            if (a[mid] <= kk + k) l = mid;
            else r = mid - 1;
        }
        res = max(res, r - i + 1);
    }
     
    printf("%.5lf", res * 1.0 / n);
     
    return 0;
}

代码二（双指针）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;
int n,k,a[100010];
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    double ans=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1,j=1;i<=n;i++)
    {
        while(a[i]-a[j]>k) j++;
        ans=max(ans,1.0*(i-j+1)/n);
    }
    cout<<ans<<"\n";
}

D：小红的排列构造

链接

题目描述

小红拿到了一个数组，她希望修改尽可能少的元素使其变成排列。你能帮帮她吗？
定义排列为一个长度为n的数组，其中 1 到n每个元素恰好出现一次。

输入描述:

1
2
3
4
第一行输入一个正整数n，代表数组的大小。
第二行输入n个正整数ai，用空格隔开。代表数组的元素。
1≤n≤105
1≤ai≤109

输出描述:

1
2
3
首先输出一个正整数m，代表操作次数。
接下来的m行，每行输出两个正整数i，用空格隔开，代表将第i个元素修改为x。
有多种合法方案时，输出任意一种均可。

示例1

输入

复制

1
2
4
1 2 3 1

输出

复制

1
2
1
1 4

说明

1
将第一个元素修改为 4 即可。

示例2

输入

复制

1
2
3
4 5 6

输出

复制

1
2
3
4
3
1 2
2 3
3 1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>

#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
PII a[N], p[N];
int st[N];
int b[N];
int n, k, kk;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x <= n) st[x] ++;
        a[i] = {x, i};
    }
    sort(a, a + n);
    for (int i = 1; i <= n; i++) {
        if (!st[i]) b[k++] = i;
    }
    
    for (int i = 1; i <= n; i++) {
        if (a[i].x <= n && st[a[i].x] > 1) {
            p[kk++] = {a[i].y, b[--k]};
            st[a[i].x]--;
        }
        else if (a[i].x <= n && st[a[i].x] == 0) p[kk++] = {a[i].y, b[--k]};
        else if (a[i].x > n)  p[kk++] = {a[i].y, b[--k]};
    }
    
    cout << kk << '\n';
    for (int i = 0; i < kk; i++) cout << p[i].x << " " << p[i].y << '\n';
    return 0;
}

E：

链接

题目描述

小红希望你构造一个无向连通图，满足共有n个点m条边，且i号节点到 1 号节点的最短路长度恰好为ai。你能帮帮她吗？

输入描述:

1
2
3
4
第一行输入两个正整数n,m，代表构造的图的点数和边数。
第二行输入n个整数ai，代表i号节点到 1 号节点的最短路。
1≤n,m≤105
a1=0，对于i≥2，1≤ai≤n

输出描述:

1
2
3
如果无解，请输出 -1。
否则输出m行，每行输出两个正整数u,v，代表节点u和节点v有一条边连接。
请务必保证不含重边和自环，否则将直接判为答案错误。

示例1

输入

复制

1
2
3 3
0 1 1

输出

复制

1
2
3
1 2
2 3
3 1

示例2

输入

复制

1
2
3 3
0 1 2

输出

复制

1
-1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>

#define x first 
#define y second
using namespace  std;
const int N = 2e5 + 10;
int dist[N];
vector<int> g[N];
int n, m, ma;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
    {
        cin >> dist[i];
        ma = max(ma, dist[i]); // 获得所有点的最大值 // 
        g[dist[i]].push_back(i);
    }
    
    if (m < n - 1) { // 如果边的数量小于结点数量 - 1，那么就无法形成一个将全部结点连通的图 //
        cout << -1;
        return 0;
    }
    vector<pair<int,int>> vis; // 存放满足条件的边 // 
    
    for (int i = 1; i <= ma; i++){ // 将所有结点和它比它距离小1的结点相连 //
        if(g[i].empty()) { // 如果出现空的情况，就意味着对于1~ma有断点的存在，那么这种情况我们就肯定无法生成一个图//
            cout << -1;
            return 0;
        } 
        for (auto j : g[i]) { // 如果不是空，就将结点和最短距离小于1的结点进行连接
            vis.push_back({g[i - 1][0], j});
        }
    }
    
    // 如果现在还有边需要相连接，那么就将同一层之间所有结点之间进行相连，因为这种连线是不存在意义的，不会影响路径大小//
    for (int i = 1; i <= ma && vis.size() < m; i++){
        for (int j = 0; j < g[i].size() && vis.size() < m; j++){
            for (int k = j + 1; k < g[i].size() && vis.size() < m; k++) {
                vis.push_back({g[i][j], g[i][k]});
            }
        }
        for (int j = 1; j < g[i].size() && vis.size() < m; j++) {
            for (int k = 0; k < g[i + 1].size(); k++) {
                vis.push_back({g[i][j],g[i + 1][k]});
            }
        }
    }

    // 如果现在还需要边进行连接，就将结点和最短距离大于1的结点进行连接 // 

    if (vis.size() < m) {
        cout << -1;
        return 0;
    }
    
    for (auto item:vis) cout << item.x << " " << item.y << '\n';
    return 0;
}