Day1

1598C - Delete Two Elements

题意:

从n个数中删除2个数，使剩下数的平均值不变。

思路：

删掉两个数平均值不变，所以这两个数的平均值等于n个数的平均值。

一开始想要直接for其中一个数，看看map里有没有另一个数，但是n个数的平均数×一个数可能会存在误差，导致不准确，不能准确定位。(好像不是x.5或者不是x.0就一定不存在应该也可以从这里下手解决)

既然不能用小数来解决，就转换思路：假设n个数和为sum，其中一个数是a，另一个数是b，如果满足条件( a + b ) / 2 = sum / n，那么就有 ( a + b ) * n = sum * 2 ，因此，只需要遍历一个a，另一个b通过 b * n = 2 * sum - a * n来获得即可。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
int a[N]; 
int main(){
	int t;
	cin>>t;
	while(t--) {
		map<ll,int> mp;
		ll n,sum=0,res=0;
		cin>>n;
		for(int i=1;i<=n;i++) {
			cin>>a[i];
			sum+=a[i];
		}
		for(int i=1;i<=n;i++) {
			ll tmp = 2 * sum - n * a[i];
			res+=mp[n*a[i]];
			mp[tmp]++;
		}
		cout<<res<<endl;
	}
	return 0;
}

总结：

分数的问题可以尝试变成整数的问题，等式的问题可以通过转换来变成更容易解决的问题，尤其为了缩减时间复杂度枚举一个数来求另一个数。

492B - Vanya and Lanterns

题意：

在n个位置有路灯，需要照亮l长的路，最小灯照亮的半径。

思路：

遍历两个路灯间的距离，把路灯间距离除以2，取最大的一个(因为要满足所有的数)，特别注意0和l的位置，特判一下即可。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1E6+5; 
double a[N];
int main(){
	int n,l;
	cin>>n>>l;
	double res = 0;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+1+n);
	for(int i=1;i<n;i++)
		res = max(res,(a[i+1]-a[i])/2);
	res = max(res,a[1]);
	res = max(res,l-a[n]);
	printf("%.9f",res);
	return 0;
}

总结：

特别注意边界的判断。

466A - Cheap Travel

题意：

共要坐n次车，坐一次需要a元，买一次票可以坐m次，一张票b元，最少需要多少钱。

思路：

需要考虑走m时买票还是单次便宜，以及少于m时买票还是单次便宜。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1E6+5; 
int main(){
	int n,m,a,b;
	cin>>n>>m>>a>>b;
	int tmp = min(b,(n%m)*a);
	cout<<min((n/m)*b+tmp,n*a);
	return 0;
}

总结：

考虑问题要全面，有‘/’和’%’两种情况的时候仔细看一点。