Burnling's Blog
0%

发表于 更新于 分类于 ，

题意简述

你有一个长度为 $n$ 的数组 $a$ 和一个整数 $k$。你还得到了一个长度为 $n$ 的二进制数组 $b$。

你最多可以进行 $k$ 次以下操作：

选择一个索引 $i$ ($1 \leq i \leq n$)，使得 $b_i = 1$。然后将 $a_i$ 增加 1（即将 $a_i$ 增加 1）。

你的得分定义为 $\max\limits_{i = 1}^{n} \left( a_i + \operatorname{median}(c_i) \right)$，其中 $c_i$ 表示通过从 $a$ 中删除 $a_i$ 获得的长度为 $n-1$ 的数组。换句话说，你的得分是所有 $1$ 到 $n$ 的 $i$ 中，$a_i + \operatorname{median}(c_i)$ 的最大值。

找出如果你最佳地执行这些操作，能达到的最大得分。

对于任意数组 $p$，$\operatorname{median}(p)$ 定义为数组中第 $\left\lfloor \frac{|p|+1}{2} \right\rfloor$ 小的元素。例如，$\operatorname{median} \left( [3,2,1,3] \right) = 2$ 和 $\operatorname{median} \left( [6,2,4,5,1] \right) = 4$。

思路分析

考虑如果不进行操作，我的得分应该为多少？

将数组按升序排序。

显然得分应该为数组最大值 $a_n$ 加上去掉 $a_n$ 后的中位数 $a_m$。

接着再考虑进行至多 $k$ 次操作后的结果。

如果 $a_n$ 是可更改的，那么每对 $a_n$ 进行一次操作都会直接使得分增加 $1$。

那么在这种情况下，对 $a_n$ 进行 $k$ 次操作一定是最优的，此时得分为 $a_n + a_m + k$。

那么如果 $a_n$ 不可更改呢？

此时我们有两条路可走。

第一条路是改最大值，即找到最大的可被修改的 $a_t$，对其进行 $k$ 次操作。

如此会浪费掉一些操作次数用来将 $a_t$ 填到 $a_n$。

第二条路是修改中位数。

修改中位数嘛，如果通过排序不太好动态去求。

我们可以二分一个中位数然后去看有几个数比它大。

如果加上 $k$ 次操作的话，我们可以从大到小寻找小于这个中位数的可修改的 $a_i$，将其修改为这个中位数。

$k$ 次操作过后，

如果有不少于 $\lfloor\dfrac{n+1}{2}\rfloor$ 个数比它大，说明这个中位数选小了，左边界右移。

否则说明中位数选大了，右边界左移。

两条路的得分取最大值即可。

代码实现

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;

const int maxN = 3e5 + 10;

struct Dt{
    int a,b,_id;
    friend bool operator < (Dt A, Dt B){
        return A.a < B.a;
    }
}A[maxN];

int B[maxN];

int N,K;

bool check(int mid){
    stack<int> s;
    while(!s.empty()) s.pop();
    int cnt = 0;
    for(int i = 1;i<=N;i++){
        if(A[i].a >= mid) cnt++;
        else if(A[i].b){
            s.push(mid-A[i].a);
        }
    }
    int kk = K;
    //这里用的是栈的后进先出的性质，用数组记一下反着找也没问题
    while(!s.empty()){
        int x = s.top();
        s.pop();
        if(kk >= x){
            kk -= x;
            cnt++;
        }
    }
    return (cnt > ((N + 1) >> 1));

}

inline void solve(){
    
    scanf("%d%d",&N,&K);
    for(int i = 1;i<=N;i++) scanf("%d",&A[i].a);
    for(int i = 1;i<=N;i++) scanf("%d",&A[i].b);
    for(int i = 1;i<=N;i++) A[i]._id = i;

    sort(A+1,A+1+N);
    int t = (N) >> 1;

    long long ans = 0;
    if(A[N].b){
        ans += A[N].a;
        ans += K;
        ans += A[t].a;
        printf("%lld\n",ans);
        return;
    }else{
        int l = 1;
        int r = 1e9;
        int aans = 0;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(check(mid)){
                l = mid + 1;
                aans = mid;
            }else{
                r = mid - 1;
                
            } 
        }
        ans = aans + A[N].a;
        for(int i = N;i>=1;i--){
            if(A[i].b){
                A[i].a += K;
                break;
            }
        }
        sort(A+1,A+1+N);
        ans = max(ans,A[N].a+A[(N)>>1].a*1ll);
        printf("%lld\n",ans);
    }

}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

发表于 更新于 分类于 ，

题意简述

ikrpprpp 发现了一个由整数组成的数组 $a$。

他喜欢公正，所以他希望将数组 $a$ 变得公平——也就是说，使其变为非递减数组。

为此，他可以在数组的某个索引 $1 \le i \le n$ 处执行一次“公正行为”，将 $a_i$ 替换为 $a_i ^ 2$（即将位置 $i$ 处的元素替换为它的平方）。

请问最少需要多少次公正行为才能使数组变为非递减数组？

思路分析

首先是最简单最直接的想法：暴力模拟。

如果 $ai \lt a{i-1}$，那么就进行若干次 $ai \gets a{i-1}^2$ 直至 $ai \ge a{i-1}$。

这样的缺点是显而易见的，即会轻易地爆掉 int ，甚至 long long。

那么如何缩小这个值域呢？

容易想到，如果为每一个 $a_i$ 都套上一个 $\log$，那么平方操作就变成了乘法操作。

更具体地，$\log_2 a_i^2 = 2 \log_2 a_i$。

但是还不够。long long 类型最多只够进行 63 次操作，这对于 $n \leq 2\cdot10^5$ 显然是不够用的。

既然如此，我们就可以再套一个 $\log$，把乘法操作变成加法操作。

即 $\log_2(\log_2 a_i^2)=\log_2(\log_2 a_i) + 1$。

考虑到浮点数的精度问题，我使用了二分来找每一个 $a_i$ 都需要加多少。

代码展示

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
#include<bits/stdc++.h>
using namespace std;

const int maxN = 3e5 + 10;
const double eps = 1e-7;
const double log2 = log(2);

int A[maxN];
double B[maxN];

inline void m_solve(){
    int N;
    scanf("%d",&N);
    for(int i = 1;i<=N;i++) scanf("%d",&A[i]);

    for(int i = 2;i<=N;i++){
        if(A[i] == 1 && A[i] < A[i-1]){
            printf("-1\n");
            return;
        }
    }


    for(int i = 1;i<=N;i++) B[i] = log(log(A[i])/log2)/log2;

    long long cnt = 0;
    

    for(int i = 2;i<=N;i++){
        if(A[i] == A[i-1]) continue;
        long long l = 0;
        long long r = 20000000000;
        long long ans = 0;
        while(l <= r){
            long long mid = (l + r) >> 1;
            if(B[i] + mid > B[i-1] || fabs(B[i]-B[i-1]+mid) < eps){
                r = mid - 1;
                ans = mid;
            }else l = mid + 1;
        }
        cnt += ans;
        if(ans != 0) A[i] = -1;
        B[i] += ans;
    }
    printf("%lld\n",cnt);
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) m_solve();
    return 0;
}

发表于 更新于 分类于 ，

题意简述

有一个包含 $n$ 个房间的公寓，每个房间的灯最初都是关着的。

公寓的主人决定在每个房间安装一个芯片，每个房间安装芯片的时间不同。具体来说，时间用数组 $a_1, a_2, \ldots, a_n$ 表示，其中 $a_i$ 是在第 $i$ 个房间安装芯片的时间（分钟）。

一旦芯片安装完成，它每隔 $k$ 分钟改变一次房间的灯状态——亮灯 $k$ 分钟，然后熄灯 $k$ 分钟，再亮灯 $k$ 分钟，以此类推。也就是说，第 $i$ 个房间的灯状态会在时间点 $a_i$，$a_i + k$，$a_i + 2k$，$a_i + 3k$，…… 发生改变。

求使所有房间的灯都亮着的最早时刻。

思路分析

我们注意到每盏灯的亮暗切换周期都是 $2k$，即 $t+2k$ 时的亮暗情况与 $t$ 时刻的亮暗情况相同。

既然灯的亮暗存在周期性变化，所以我们可以把 $n$ 盏灯的亮暗周期同步到一个相近的区间内。

这一部分可以通过 $a_i \gets (a_i \bmod 2k)$ 来实现。

这一操作同时也获得了 $[0,2k)$ 内每个时刻有多少盏灯恰好切换至亮灯状态。

令 $b_t$ 表示 $t$ 时刻有多少盏灯切换至亮灯状态。

可知 $bt = \sum\limits{i=0}^{2k-1} [t=(a_i \bmod 2k)]$。

接下来考虑如何统计。

因为每盏灯亮暗切换间隔为 $k$ 秒，所以我们可以统计一个长度为 $k$ 的时间区间内所有灯的亮暗情况。

如果一盏灯在左端点的时刻亮了，那么它正好会在右端点的时刻后一个时刻灭掉。

如果一盏灯被点亮的时间落在这个长度为 $k$ 的区间内，那么在右端点时，这盏灯一定还是亮着的。

如果这个区间内并不是所有的灯都亮着，我们就让这个区间向右移动一位。

如果在这个区间内，所有灯都亮着，那么这个区间的右端点即为一个答案。

因为上一次的移动添加了新的右端点后才使得所有灯都亮着，所以当前区间的右端点即为所求的最小的等待时间。

代码实现

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
#include<bits/stdc++.h>
using namespace std;

const int maxN = 6e5 + 10;
int A[maxN];
int num[maxN];

inline void solve(){
    int N,K;
    scanf("%d%d",&N,&K);
    for(int i = 1;i<=N;i++) scanf("%d",&A[i]);
    for(int i = 0;i<=(K<<1);i++) num[i] = 0;

    int ma = -1;

    for(int i = 1;i<=N;i++){
        num[A[i] % (K << 1)]++;
        ma = max(ma,A[i]);
    }

    int cnt = 0;
    int ans = INT_MAX;

    for(int i = 0;i<= (K - 2);i++) cnt += num[i];

    int l = 0;
    int r = K - 1;

    while(l < (K << 1)){
        if(r >= (K << 1)) r -= (K << 1);

        cnt += num[r];

        if(cnt == N){
            int wait = (r - ma) % (K << 1);
            if(wait < 0) wait += (K << 1);
            ans = min(ans,ma+wait);
        }

        cnt -= num[l];

        l++,r++;
    }
    
    if(ans == INT_MAX) ans = -1;

    printf("%d\n",ans);

}

int main(){
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

发表于 更新于 分类于 ，

题目链接

思路分析

题目不好好读完是这样的。

提示中提到，不存在两个查询都满足 i != j 且 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]。

也就是说，两条新增道路之间的关系仅有被包含与不相交，不存在相交的区间。

那么对于一条新添加的 $u\to v$ 的边，它可以替代掉起终点落在 $[u,v]$ 区间内的所有边。

模拟即可。复杂度为 $O(n)$。因为至多删掉 $n-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
class Solution {
public:
    set<pair<int,int>> G;
    vector<int> lftp;

    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        vector<int> ans;
        for(int i = 1;i<n;i++) G.insert(make_pair(i,i+1));
        
        for(auto query : queries){
            int u = query[0] + 1;
            int v = query[1] + 1;

            auto it = G.lower_bound(make_pair(u,-1)); //找到第一条

            if(it != G.end() && it->first == u && it->second < v){
                while(it != G.end() && it->first < v) it = G.erase(it);
                G.insert(make_pair(u,v));
            }

            ans.push_back(G.size());
        }
        return ans;
    }
};

发表于 更新于 分类于 ，

题意简述

Monocarp 正在玩一款电脑游戏，起始时他的等级为 1。他将按顺序与 $n$ 只怪物战斗，第 $i$ 只怪物的等级为 $a_i$。

每只怪物的遭遇顺序如下：

  • 如果 Monocarp 的等级严格高于怪物的等级，怪物逃跑；

  • 否则，Monocarp 与怪物战斗。

每经过 $k$ 次战斗（逃跑的怪物不计算在内），Monocarp 的等级增加 1。所以在战斗了 $k$ 只怪物后他的等级变为 2，战斗了 $2k$ 只怪物后他的等级变为 3，依此类推。

你需要处理 $q$ 个查询，每个查询的形式为：
$i~x$: 如果参数 $k$ 等于 $x$，第 $i$ 只怪物会与 Monocarp 战斗还是逃跑？

思路分析

不太会。

但在洛谷看到 一篇题解 感觉很神秘很厉害。

通过题目容易知道，$k$ 越小，升级越快，逃跑的怪物会越多。

对于每一只怪物，都存在一个最大的 $k_i$，当 $k \leq k_i$ 时，怪物必定会逃跑。

那么这个 $k_i$ 就可以通过二分答案找出来。

然后考虑怎么 $\text{check}$。

对于第 $i$ 只怪物前面的 $i-1$ 只怪物，我们已经知道了它们对应的 $k_j$。

那么第 $i$ 只怪物时经历过的战斗数即为 $\sum\limits_{j=1}^{i-1} [k_j \leq k_i]$ 。

换言之，战斗数即为前 $i-1$ 个 $k_j$ 中小于 $k_i$ 的个数。

再换言之，以上可以视为求前 $i-1$ 个 $k_j$，有多少个落在了 $[1,k_i-1]$ 区间内。

这个可以拿树状数组求。

提交记录