拼多多笔试ak
一二题比较简单
三：贪心+排序
#include<bits/stdc++.h>
using namespace std;
char s[10100];
struct node{
int val;
int pos;
}arr[10100];
int vis[15][10100],p;
bool cmp(node x,node y){
if(abs(x.val-p) == abs(y.val-p)){
if(x.val == y.val){
if(x.val < p) return x.pos>y.pos;
else return x.pos < y.pos;
}else{
if(x.val < y.val && x.pos < y.pos){
return x.pos > y.pos;
}else if(x.val > y.val && x.pos > y.pos){
return x.pos > y.pos;
}else if(x.val < y.val && x.pos > y.pos){
return x.pos < y.pos;
}else{
return x.pos < y.pos;
}
}
}
return abs(x.val-p) < abs(y.val-p);
}
int ans[15];
char cp[10100];
int main(){
int n,k;
scanf("%d%d",&n,&k);
scanf("%s",s);
for(int i=0;i<n;++i){
arr[i].pos = i;
arr[i].val = s[i] - '0';
}
int minn = -1;
for(int i=0;i<=9;++i){
p = i;
sort(arr,arr+n,cmp);
for(int j=0;j<k;++j){
ans[i] += abs(arr[j].val - i);
}
for(int j=0;j<n;++j){
vis[i][j] = arr[j].pos;
}
if(minn == -1) minn = ans[i];
minn = min(minn,ans[i]);
}
cout<<minn<<endl;
char Ans[10100] = "#";
for(int i=0;i<=9;++i){
if(ans[i] == minn){
strcpy(cp,s);
int x;
for(int j=0;j<n;++j){
if(j < k) {
cp[vis[i][j]] = i + '0';
}
}
if(Ans[0] == '#'){
strcpy(Ans,cp);
}else if(strcmp(Ans,cp) > 0){
strcpy(Ans,cp);
}
}
}
cout<<Ans<<endl;
return 0;
}
四：n只有1e5，map离散化
然后暴力
数据有点水吧 当时想暴力骗分，结果就过了，可能数据是随机的，没有手造
如果是很多个1 2 1 2 ....这种的，肯定超时
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
map<int,int>mp;
vector<int>vt[maxn];
int s[maxn];
int num[maxn];
int main(){
int n,k,tot=0;
scanf("%d%d",&n,&k);
for(int i=1,p=0;i <= n;++i){
scanf("%d",&s[i]);
p++;
if(mp.count(s[i]) == 0) mp[s[i]] = ++tot;
if(s[i+1] != s[i]){
num[i] = p;
p = 0;
vt[mp[s[i]]].push_back(i);
}
}
int ans = 0;
for(int i=1;i<=tot;++i){
int Size = vt[i].size();
bool flag = 0;
for(int j=0;j<Size;++j){
int tmp = k;
int sum = 0;
for(int z=j;z<Size&&tmp>=0;++z){
sum += num[vt[i][z]];
if(z != Size - 1) tmp -= vt[i][z+1] - num[vt[i][z]] - vt[i][z];
}
ans = max(ans,sum);
}
}
cout<<ans<<endl;
return 0;
}
