序列处理
/*
给定一个长度为 n 的整数序列 a1,a2,…,an。
我们可以对该序列进行修改操作，每次操作选中其中一个元素，并使其增加 1。
现在，请你计算要使得序列中的元素各不相同，至少需要进行多少次操作。
输入格式
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
输出格式
一个整数，表示所需的最少操作次数。
数据范围
前 6 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤3000，1≤ai≤n。
输入样例1：
4
1 3 1 4
输出样例1：
1
输入样例2：
5
1 2 3 2 5
输出样例2：
2
*/
/*
排序，然后每次都跟前面一个比较
*/
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
cin>>n;
const int N=3010;
int a[N];
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
int ans=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i]==a[j]){
a[j]++;
ans++;
}
}
}
cout<<ans;
return 0;
}
数字重构
数字重构
思考
本题看到正确作答率很低后，我也就没有仔细思考，其实思路并不难想。
反思一下，如果拿到一个没法一眼看出来怎么做的题目，应该如何思考。首先看看是否可以直接模拟出来，注意观察数据量，模拟很可能超时。下图是我在网上找到的一幅蓝桥杯考点图，出处。然后考虑是否可以使用递归、dp、搜索，如果都很困难，可以思考二分答案是否能做。本题就是将第一个数进行排列组合，很容易想到全排列，也就是使用dfs求解。
这思路很好想，接下来的代码也很好写，我的这个代码应该是对的，不过超时了，超时的点结果也是对的。
代码1
/*
给定两个正整数 a 和 b，均不含前导 0。
现在，请你对 a 进行重构，重新排列其各位数字顺序，得到一个不含前导 0 的新正整数。
要求新正整数在不超过 b 的前提下，尽可能大。
输出新正整数。
注意，我们允许新正整数等于 a，即保持原样不变。
输入格式
第一行包含一个正整数 a。
第二行包含一个正整数 b。
两个输入数字均不含前导 0。
输出格式
一个不含前导 0 的正整数，表示答案。
数据保证一定有解。
数据范围
前 6 个测试点满足 1≤a,b≤10^9。
所有测试点满足 1≤a,b≤10^18。
输入样例1：
123
222
输出样例1：
213
输入样例2：
3921
10000
输出样例2：
9321
输入样例3：
4940
5000
输出样例3：
4940
*/
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=20;
long long a,b;
int d[N];
int judge[N];
int n=1;
long long ans=0;
void dfs(long long sum,int x){
//sum是当前dfs的数字的值，x是当前的位数
if(x==n+1){//如果dfs了n位
if(sum<=b){
ans=max(sum,ans);
}
return ;
}
//dfs过程：
for(int i=1;i<=n;i++){
if(judge[i]==0){
//如果某个没有被用过
judge[i]=1;
dfs(sum+d[i]*pow(10,x-1),x+1);
judge[i]=0;
}
}
}
int main(){
cin>>a>>b;
while(a!=0){
d[n]=a%10;
a/=10;
n++;
}//d[]中存着a的各个位置上的数
n--;
for(int i=1;i<=n;i++){
dfs(0,1);
}
cout<<ans;
return 0;
}
超时情况：
然后我想着优化，突然发现，这个难道不能直接从大到小全排列吗，如果遇到满足要求的直接
**exit(0)退出程序**
在写代码的时候我发现降序的全排列并不能用原来的sum完成，具体原因难以打字描述，自己实验一下吧。
于是我换成了存进数组的方法。不过还是超时了，但是时间上提高了5倍多。
/*
给定两个正整数 a 和 b，均不含前导 0。
现在，请你对 a 进行重构，重新排列其各位数字顺序，得到一个不含前导 0 的新正整数。
要求新正整数在不超过 b 的前提下，尽可能大。
输出新正整数。
注意，我们允许新正整数等于 a，即保持原样不变。
输入格式
第一行包含一个正整数 a。
第二行包含一个正整数 b。
两个输入数字均不含前导 0。
输出格式
一个不含前导 0 的正整数，表示答案。
数据保证一定有解。
数据范围
前 6 个测试点满足 1≤a,b≤10^9。
所有测试点满足 1≤a,b≤10^18。
输入样例1：
123
222
输出样例1：
213
输入样例2：
3921
10000
输出样例2：
9321
输入样例3：
4940
5000
输出样例3：
4940
*/
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=20;
long long a,b;
int d[N];
int judge[N];
int n=1;
long long ans=0;
int m[N];
bool cmp(int x,int y){
return x>y;
}
void dfs(int m[],int x){
//sum是当前dfs的数字的值，x是当前的位数
if(x==n+1){//如果dfs了n位
long long sum=0;
for(int i=1;i<=n;i++){
sum+=m[i]*pow(10,n-i);
}
if(sum<=b){
cout<<sum;
exit(0);
}
return ;
}
//dfs过程：
for(int i=1;i<=n;i++){
if(judge[i]==0){
//如果某个没有被用过
judge[i]=1;
m[x]=d[i];
dfs(m,x+1);
judge[i]=0;
}
}
}
int main(){
cin>>a>>b;
while(a!=0){
d[n]=a%10;
a/=10;
n++;
}//d[]中存着a的各个位置上的数
n--;
sort(d+1,d+1+n,cmp);
for(int i=1;i<=n;i++){
dfs(m,1);
}
cout<<ans;
return 0;
}
看了题解后的做法
此做法使用了字符串，避免了用pow求值的麻烦
思路是贪心，看某一位能放的最大的数是几
详细讲解在代码中体现
这里是几个重要的代码模板
对字符串降序排列sort(a.begin(),a.end(),greater<char>（）)
上面那个括号别忘了
遍历元素类型特殊的
for(auto c:a)
转化为string类型的
string res =to_string(x);
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int cnt[10];
string get_min(int x){
//返回值是string
string res =to_string(x);
cnt[x]--;//因为使用了，数量减少
for(int i=0;i<10;i++)
//第一个遍历是从所有小的数开始枚举
for(int j=0;j<cnt[i];j++)
//第二个遍历是确定这个数最多能用几个
res+=to_string(i);
cnt[x]++;//因为上边getmin只是模拟一下，后面还可能需要x，因此要恢复
return res;
}
int main(){
string a,b;
cin>>a>>b;
if(a.size()<b.size()){
//如果a的位数比b小，那么就直接排列a最大的情况
sort(a.begin(),a.end(),greater<char>());
//排序语法要记住
cout<<a<<endl;
}
else{
for(auto c:a) cnt[c-'0']++;
string res;
for(int i=0;i<a.size();i++)
//第一个遍历每个位置
for(int j=9;j>=0;j--)
//第二个遍历每个位置上数字，尽量取大的
if(cnt[j]&&res+get_min(j)<=b){
//这个判断是说，如果j这个数存在
//并且它出现在这个位置上时组成的数中有能满足要求小于b的
//(因此是get_min，就是只要找到最小的能满足就行)
//并且提醒string可以直接判断大小，很方便的
res+=to_string(j);//我们只用这个数（就是如果这个数能用就选它）
cnt[j]--;
break;
}
cout<<res<<endl;
}
return 0;
}