CF1769B1 Копирование файлов I 题解

题目链接

题目大意

从小到大输出满足 \(\frac{100 \times x}{a_i}=\frac{100 \times (\sum_{j=1}^{i-1} a_j+x)}{\sum a_j}\) 时它们的值。

思路

看到数据范围 \(n\leq 100\)，考虑暴力枚举传输每一个字节时的情况，判断 \(a\) 和 \(b\) 的值是否相等即可。

对于答案，我们使用 set 来储存，它可以实现自动去重与排序的功能，大大减少了代码的复杂度。

于是乎，我写出了第 \(1\) 份代码：

#include<bits/stdc++.h>
using namespace std;
int n,a,b,z[105];
set<int>y;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>z[i];
	for(int i=1;i<=n;i++){
		for(int j=0;j<=z[i];j++){
			a=100*j/z[i];
			int tot=0,tot2=0;
			for(int k=1;k<=i-1;k++) tot+=z[k];//区间求和
			for(int k=1;k<=n;k++) tot2+=z[k];//区间求和
			b=(100*(tot+j))/tot2;
			if(a==b) y.insert(a);//判断
		}
	}
	for(auto i:y) cout<<i<<endl;//遍历并输出
	return 0;
}

仔细观察，我们发现这份代码其实是 \(O(n^2 \sum z_i)\) 的，虽然可过，但仍有更优解法。

观察这两行代码：

for(int k=1;k<=i-1;k++) tot+=z[k];
for(int k=1;k<=n;k++) tot2+=z[k];

我们发现，这两行代码起到的是区间求和的作用，我们可以使用前缀和优秀的 \(O(1)\) 区间求和能力来优化本题代码。可达到 \(O(n \sum z_i)\) 的时间复杂度。

参考代码（请勿抄袭）：

#include<bits/stdc++.h>
using namespace std;
int n,a,b,z[105],sum[105];//z代表当前字节数，sum数组记录前缀和 
set<int>y;//STL神器 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>z[i];
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+z[i];//处理前缀和 
	for(int i=1;i<=n;i++){//每个文件 
		for(int j=0;j<=z[i];j++){//每个文件的字节 
			a=100*j/z[i];
			b=(100*(sum[i-1]-sum[0]+j))/(sum[n]-sum[0]);//前缀和快速求区间和 
			if(a==b) y.insert(a);//放入set中，自动去重+排序 
		}
	}
	for(auto i:y) cout<<i<<endl;//遍历并输出 
	return 0;
}