求救SA(回复关注)
查看原帖
求救SA(回复关注)
1039862
Stugeon楼主2024/7/4 18:31

我的SA只拿到了50分,求大佬调qwq1. ```cpp

#include <cmath>
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <bits/stdc++.h>
using namespace std;
int n,m,tot;
double a[25];
double mid;
double ans = 100000.0;
inline double dread()
{
	double f = 1,x = 0;
	char s = getchar();
	while (s < '0' || s > '9')
	{
		if (s == '-')
		{
			f = -f;
		}
		s = getchar();
	}
	while (s >= '0' && s <= '9')
	{
		x = x * 10 + s - '0';
		s = getchar();
	}
	return x * f;
}
inline int iread()
{
	int f = 1,x = 0;
	char s = getchar();
	while (s < '0' || s > '9')
	{
		if (s == '-')
		{
			f = -f;
		}
		s = getchar();
	}
	while (s >= '0' && s <= '9')
	{
		x = x * 10 + s - '0';
		s = getchar();
	}
	return x * f;
}
int Rand()
{
	return rand() % n + 1;
}
double Randx()
{
	return (double)rand() / RAND_MAX;
}
double count()
{
	int l = 1;
	double sum1 = 0.0,sum2 = 0.0;
	for (register int i = 1 ; i <= n ; i++)
	{
		if (i - l + 1 == tot)
		{
			l = i + 1;
			sum1 += a[i];
			sum2 += (mid - sum1) * (mid - sum1);
			sum1 = 0.0;
		}
		else
		{
			sum1 += a[i];
		}
	}
	if (n % m != 0)
	{
		sum2 += (mid - sum1) * (mid - sum1);
	}
	sum2 = sum2 / m;
	sum2 = sqrt(sum2);
	return sum2;
}
void SA()
{
	double T = 2619.0;
	int left,right;
	double p;
	while (T > 1e-10)
	{
		left = Rand();
		right = Rand();
		swap(a[left],a[right]);
		p = count();
		if (p < ans)
		{
			ans = p;
		}
		else if (exp((ans - p)/T) < Randx())
		{
			swap(a[left],a[right]);
		}
		T *= 0.997;
	}
}
int main()
{
	srand(time(NULL));
	n = iread(),m = iread();
	if (n % m == 0)
	{
		tot = n / m;
	}
	else
	{
		tot = n / m + 1;
	}
	for (register int i = 1 ; i <= n ; i++)
	{
		a[i] = dread();
		mid += a[i];
	}
	mid /= m;
	while ((double)clock()/CLOCKS_PER_SEC < 0.95)
	{
		SA();
	}
	printf("%.2lf",ans);
	return 0;
}
2024/7/4 18:31
加载中...