Kevin的矩阵【牛客tracker 每日一题】
Kevin的矩阵
时间限制：3秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
氧气少年现在有一个长度为n nn的序列a aa和一个空的矩阵，矩阵的行数不限，但列数为m mm。
每次操作他可以从下面的操作中任选其一：
- 任选序列的某个位置，将此位置的数字修改为任意的数字；
- 将矩阵的列数增加1 11；
- 将矩阵的列数减小1 11（如果当前矩阵的列数大于1 11）。
操作完成后，氧气少年将序列中的每个元素依次按照从上到下、从左到右的顺序填到矩阵中。（即：先填第1 11行第1 11列，再填第1 11行第2 22列，…… 填第1 11行第m mm列，填第2 22行第1 11列，填第2 22行第2 22列，…… 填第2 22行第m mm列，以此类推。）
氧气少年想要让矩阵至少一列的所有数字均为目标数字k kk，请求出他需要做的最少的操作次数。
例如，当a = [ 1 , 2 , 3 , 4 , 5 , 1 , 6 , 7 , 8 , 9 , 1 , 2 , 3 , 4 , 5 , 8 , 9 ] , m = 4 , k = 1 a=[1,2,3,4,5,1,6,7,8,9,1,2,3,4,5,8,9],m=4,k=1a=[1,2,3,4,5,1,6,7,8,9,1,2,3,4,5,8,9],m=4,k=1时，如果不执行任何操作，填数后的矩阵如下图所示：
如果在填数之前，先将a 16 a_{16}a16改为1 11，再将矩阵的列数增加为5 55，那么填数后的矩阵如下图所示：
注意到此时第一列的所有数字均为目标数字1 11，符合要求，并且没有比这耗费次数更少的操作方案。因此答案为2 22。
例如，当a = [ 1 , 2 , 3 , 4 , 5 ] , m = 3 , k = 3 a=[1,2,3,4,5],m=3,k=3a=[1,2,3,4,5],m=3,k=3时，如果不执行任何操作，填数后的矩阵如下图所示：
注意到此时第三列的所有数字均为目标数字3 33，符合要求。因此答案为0 00。
输入描述：
第一行包含一个整数T ( 1 ≤ T ≤ 10 5 ) T(1≤T≤10^5)T(1≤T≤105)，表示测试用例的组数。
对于每组测试用例：
第一行包含三个整数n ( 1 ≤ n ≤ 2 ⋅ 10 5 ) , m ( 1 ≤ m ≤ 10 9 ) , k ( 0 ≤ k ≤ 10 9 ) n(1≤n≤2⋅10^5),m(1≤m≤10^9),k(0≤k≤10^9)n(1≤n≤2⋅105),m(1≤m≤109),k(0≤k≤109)，分别表示序列的长度，初始矩阵的列数和目标数字。
第二行包含n nn个整数a 1 … a n ( 0 ≤ a i ≤ 10 9 ) a_1…a_n(0≤a_i≤10^9)a1…an(0≤ai≤109)，表示该序列。
保证对于所有的测试用例，n nn的总和不超过2 ⋅ 10 5 2⋅10^52⋅105。
输出描述：
对于每组测试用例：
仅输出一行，包含一个整数，表示答案。
示例1
输入：
2 17 4 1 1 2 3 4 5 1 6 7 8 9 1 2 3 4 5 8 9 5 3 3 1 2 3 4 5输出：
2 0说明：
样例解释见题目描述。
解题思路
本题核心是枚举新列数+统计列修改代价求解最小操作次数：要让矩阵某一列全为目标数k，总操作次数 = 该列非k元素的修改次数 + 调整矩阵列数的代价（|新列数j - 原列数m|）。由于j超过n时每列仅1 11个元素，无优化空间，因此仅枚举j ≤ min(n, 2000)即可覆盖最优解。对每个枚举的j，遍历所有列c，统计序列中c、c+j、c+2j...位置的非k元素数量（修改代价），计算总代价并维护最小值。该方法通过范围剪枝大幅降低计算量，时间复杂度适配n总和≤ 2 e 5 ≤2e5≤2e5、T≤1e5的规模，精准找到最小操作次数。
总结
- 核心逻辑：总操作次数由数字修改次数和列数调整代价组成，遍历所有合法列数
j，计算每列的总代价取最小值。 - 关键优化：仅枚举
j≤2000，跳过无优化意义的大列数，避免超时。 - 效率保障：剪枝后枚举量极小，线性统计修改次数，完美适配题目大数据量的输入要求。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=2e5+10;constll mod=1e9+7;constll INF=1e18;ll pre[N];intmain(){ll T;cin>>T;while(T--){ll n,m,k;cin>>n>>m>>k;vector<ll>a(n+1);pre[0]=0;for(ll i=1;i<=n;i++){cin>>a[i];pre[i]=pre[i-1]+(a[i]!=k);}ll ans=1e18;ll mx=min(n,2000ll);for(ll j=1;j<=mx;j++){for(ll c=1;c<=min(j,n);c++){ll cnt=0;for(ll i=c;i<=n;i+=j)cnt+=(a[i]!=k);ans=min(ans,cnt+abs((ll)j-m));}}cout<<ans<<endl;}return0;}