拼多多笔试
2h
4算法
一
题目大意
有n个物品，每个物品都有一个价格，买3个送价格最便宜的那一个，问最少花多少钱能够获得者n个物品
思路
贪心
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const int maxn = 2e5+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
using namespace std;
int a[maxn];
bool cmp(int a, int b)
{
return a>b;
}
int main()
{
IO;
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1, a+n+1, cmp);
ll ans = 0;
for(int i=1;i<=n;i+=3)
{
ans += a[i];
if(i+1<=n)ans += a[i+1];
}
cout<<ans<<"\n";
return 0;
}
二
题目大意
给一个长度为n的数组，求子数组和能被M整除的个数，n的范围是1e5，m的范围是100，数值的范围是1e9
思路
不太会，写了个暴力骗了60%
三
题目大意
给一个长度为n的十进制字符串s，要使得某个数字的个数出现至少k次，可以将字符串中的数字改变成0至9的任意一个，改变需要花费两数值差的绝对值，比如将1变成2，则花费1，你需要花费最少，并且输出字典序最小的结果。字符串的长度范围是1e4
思路
求出0至9出现k次的代价，然后输出最小代价的串即可。假设现在需要5的次数出现k次，那么4和6变成5的代价都是1，但是结果需要字典序最小，所以我们肯定希望优先将6变成5而不是将4变成5。这样就可以求出花费最小的串。最后还需要对花费最小的串做一下处理，因为这个串不一定是花费最小且字典序按序最小，假设原字符串的两个位置的字符i和j都相等，但是变化后的字符串的位置i的字典序大于j，那么我们可以交换变化后的字符串i和j的位置，因为要字典序最小，所以要将小的字符放前面，大的放后面，因为在原字符串中i和j相同，所以可以这样交换。
AC代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const int maxn = 2e5+5;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
using namespace std;
int n, k;
string s;
struct node
{
//id是字符所在的序号
//v是原字符和变换后的字符的差值的绝对值
//tv是原字符-变化后的字符，即不带绝对值的v
int id, v, tv;
node(int vv=0, int ii=0, int tt=0)
{
v = vv; id = ii; tv=tt;
}
};
bool cmp(node a, node b)
{
if(a.v != b.v) return a.v < b.v;
if(a.tv != b.tv) return a.tv > b.tv;
return a.id < b.id;
}
vector<pair<int, string> > res;
void slove(int x)
{
vector<node> tmp;
//计算出每个字符变换成x的代价，根据cmp的规则排序
for(int i=0;i<n;i++)
{
tmp.push_back(node(abs(s[i]-'0'-x), i, s[i]-'0'-x));
}
sort(tmp.begin(), tmp.end(), cmp);
int sum = 0;
string str = s;
for(int i=0;i<k;i++)
{
sum += tmp[i].v;
str[tmp[i].id] = (char)(x+'0');
}
res.push_back(make_pair(sum, str));
}
int main()
{
cin>>n>>k>>s;
for(int i=0;i<=9;i++)
slove(i);
sort(res.begin(), res.end());
string ans = res[0].second;
//对花费最少的串做处理，变成字典序最小
for(int i=0;i<n;i++)
{
for(int j=n-1;j>i;j--)
{
if(s[i] == s[j] && ans[i]>ans[j])
{
swap(ans[i], ans[j]);
break;
}
}
}
cout<<res[0].first<<"\n"<<ans<<"\n";
return 0;
}
四
题目大意
有一个长度为n的数组，你最多可以删除k个位置的值，求最长的子串且子串中的数字都相同
思路
不会，乱搞骗了20%