最佳牛围栏

最佳牛围栏

解题思路

分析题目，首先我们指导题目给我们一串数字，这个数字有n个，并且都是1≤x≤20001\leq x\leq 2000的，现在要找到一个连续字串，该字串的长度大于等于F，要使得这个连续字串的平均值最大。

这个可以用二分的思路进行寻找，我们的数字最小为1，最大为2000，我们取出边界的中间值，1000，然后使用1000减去这一串数字，使用前缀和sum来存取减去后的数字。我们使用双指针i，j，i从0开始，j从F开始，i,j同时移动，每次确认0~i区间内的最小值minsum ，若满足条件sum[j]-minsum>0则说明这段区间的平均值比当前的二分平均值大，因此就将l变换到mid再次进行二分，否则就将r变换到mid，进行二分。

(ps:我也不知道自己在说什么)

AC代码

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 <bits/stdc++.h>
using namespace std;
const int N = 100010;
// 区域数和最小连续区间数
int n,f;
// 每片区域的牛
int d[N];
// 前缀和数组
double sum[N];

bool check(double x){
    // 先计算每片区间内的数减去均值的前缀和
    for(int i =1;i<=n;i++)sum[i] = d[i]+sum[i-1]-x;
    // 记录0~j-f的区域内的最小的区域和
    double minv = 0;
    for(int i = 0,j=f;j<=n;j++,i++){
        // 每次都记录最小的区域和
        minv = min(minv,sum[i]);
        // 如果我们存在一个区间使得所有数的加和都大于0
        if(sum[j] >= minv)return true;
    }
    return false;
}


int main(){
    cin>>n>>f;
    
    for(int i = 1;i<=n;i++)cin>>d[i];
    // 区间的中间值
    double l = 0,r = 2000;
    while(r-l>1e-5){
        // 开始二分
        double mid = (l+r)/2;
        // 确认在给定区间内的均值上界是否大于mid
        if(check(mid))l = mid;
        else r = mid;
    }
    cout<<int(r*1000)<<endl;
    return 0;
}

特殊排序

特殊排序

AC代码

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
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res;
        // 使用二分插入排序进行排序
        // 先插入第一个数
        res.push_back(1);
        for(int i =2;i<=N;i++){
            // 获取已经排序好的数组
            int l = 0, r = res.size()-1;
            // 二分寻找应该插入的位置
            while(l < r){
                int mid = l+r+1>>1;
                if(compare(res[mid],i))l = mid;
                else r = mid-1;
            }
            // 将i先插入序列
            res.push_back(i);
            // 将i放置到合理的位置
            for(int j = res.size()-2;j>r;j--)swap(res[j],res[j+1]);
            // 如果i比所有排好的数字都要小的话，就直接和第一个交换
            if(compare(i,res[r]))swap(res[r],res[r+1]);
        }
        return res;
    }
};

电影

电影

解题思路

今天是我第一次感觉到scanf和cin的差距

先说一下怎么写这题吧

用unordered_map存储每种语言分别能被多少人听懂，为啥不使用map？因为map查询好像没他快所以用这个。

先创建一个结构体，a,b,c,其中，a表示电影号，b表示该电影能被多少人听懂，c表示该电影能被多少人看懂

然后写个比较函数，然后用sort就结束了

不难的

你可以吧我的scanf换成cin，你试试能不能过？

还有一种方式，你用cin也可以

在using namespace std;

下面添加

#pragma GCC optimize (2)
#pragma G++ optimize (2)

然后在main里第一句添加

ios::sync_with_stdio(false);

好像就能把scanf换成cin也能a了，

你问我这东西有什么用？我也不知道，好像是优化编译的。

AC代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
unordered_map<int, int> lan;
//电影结构体
typedef struct Movie
{
    // 索引，听懂，看懂
    int index, speak, danmaku;
} movie;
movie love[N];
int n, m;
// 降序比较函数
bool cmp(movie a, movie b)
{
    if (a.speak > b.speak)
        return true;
    else if (a.speak == b.speak)
        return a.danmaku > b.danmaku;
    return false;
}

int main()
{
    // 存储每种语言分别有多少个珂学家听得懂
    scanf("%d",&n);
    for (int i = 0; i < n; i++)
    {
        int temp;
        scanf("%d",&temp);
        lan[temp]++;
    }
    // 记录每个电影分别有多少个珂学家听得懂，看得懂
    scanf("%d",&m);
    for (int i = 0; i < m; i++)
    {
        int temp;
        scanf("%d",&temp);
        love[i] = {i, lan[temp], 0};
    }
    for (int i = 0; i < m; i++)
    {
        int temp;
        scanf("%d",&temp);
        love[i].danmaku = lan[temp];
    }
    // 使用排序函数
    sort(love, love + m, cmp);
    cout << love[0].index + 1 << endl;
    return 0;
}