【牛客小白月赛117】E题—

【牛客小白月赛117】E题——种类数小结

1 初步想法

1.1 前置知识：vector数组的去重操作

unique()将不重复的元素放在数组前面，重复元素移到后面，qs获取不重复元素的后一个位置，之后用erase()函数去除重复元素。

qs=unique(a.begin()+1,a.begin()+k+1);
a.erase(qs,a.end());

1.2 模拟的解法

根据题目意思，统计数组中不同数的种类数，然后遍历数组，每次减去种类数，直到数组中的元素只有一种为止。在实现上，我的输入的数是从数组a下标1开始，所以我设置的循环条件是a.size()>2,因为a[0]=0，如果碰到输入n个相同的非零整数，此时去重后元素的个数是2。

实现代码（运行超时，只通过30%左右的数据）

#include<bits/stdc++.h>
using namespace std;
int n;
vector<long long> a(100005);
void process(){int k=a.size()-1;for(int i=1;i<=a.size();i++){if(a[i]-k>0) a[i]=a[i]-k;else a[i]=0;}vector<long long>::iterator qs;sort(a.begin()+1,a.begin()+k+1);qs=unique(a.begin()+1,a.begin()+k+1);a.erase(qs,a.end());
}
int main(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];vector<long long>::iterator qs;sort(a.begin()+1,a.begin()+n+1);qs=unique(a.begin()+1,a.begin()+n+1);a.erase(qs,a.end());long long cnt=0;while(a.size()>2){process();cnt++;}cout<<cnt;return 0;
}

不过这种解法的问题是会超时，数据规模是10的5次方，main函数的while循环加上函数process()里面也有一重循环，效率不高，要想一种新的解法。

2 新方法

2.1 新方法的思想

我设计以下测试样例：

测试样例1
4
100 200 300 400

对于测试样例1，排序后，我们知道100是最先变化为0的，100在减小为0的过程中，种类数已知是4个，所以，100减为0需要进行100/4=25次操作。之后在剩下的数中，100减为0后依次变为100，200，300（是所有数同时减100），对于这里的100要变成0，因为目前数组有4，100，200，300这4种数，需要经过100/4=25次操作。之后，剩下的数以此为100，200，因为目前数组有4，100，200这3种数，100变成0需要经过100/3+1=34次操作（目前数组有），然后剩下一个数98，需要经过98/2=49次操作。一共是25+25+34+49=133次操作。通过这样的做法我们可以降低时间复杂度。

2.2 新方法的实现

为了实现新方法，在数组各元素减为0的过程中，我们要设置几个变量：
ans：最终结果
sum：累计减少量
cnt：当前的种类数，对于非0元素，如果不是第一个，因为前面的数已经变成0，所以非第一个数需要+1，把0算进去。cnt=a.size()-i+(i!=0);
x：表示当前的数变为0需要操作的次数，我们需要向上取整：x=(a[i]-sum+cnt-1)/cnt。

实现代码

#include<bits/stdc++.h>  // 包含所有标准库头文件
#define LL long long    // 定义长整型别名
int n;
using namespace std;int main(){cin>>n;  // 输入数组长度vector<LL> a(n);  // 创建长度为n的长整型向量for(int i=0;i<n;i++) cin>>a[i];  // 输入数组元素// 排序并去重，确保数组是升序且无重复元素sort(a.begin(),a.end());a.erase(unique(a.begin(),a.end()),a.end());// 如果数组只有一个元素，直接输出0if(a.size()==1)cout<<0<<endl;else{LL ans=0,sum=0,cnt=0;  // ans:结果，sum:累计减少量，cnt:当前影响的元素数量// 遍历去重后的数组for(int i=0;i<n;i++){// 如果当前元素减去累计减少量已经小于0，跳过if(a[i]-sum<0) continue;// 计算当前影响的元素数量：剩余元素数 + (如果不是第一个元素，还包括之前的元素)cnt=a.size()-i+(i!=0);// 计算需要多少次操作才能将当前元素减为0// (a[i]-sum+cnt-1)/cnt 是向上取整的技巧LL x=(a[i]-sum+cnt-1)/cnt;ans+=x;  // 累计操作次数sum+=x*cnt;  // 更新累计减少量}cout<<ans<<endl;}return 0;
}