我在下面先前的代码加了个
sort(arr+1,arr+1+n);reverse(arr+1,arr+1+n);
由80pt变成100pt??!!
为什么?!?!
原先的
#include<bits/stdc++.h>
#define int long long
#define inf 1e9
using namespace std;
int arr[22], brr[22], n, m; double sum, tempans, ans;
double calc() {
priority_queue<int> que;
for(int i=1; i<=m; ++i) que.push(0);
for(int i=1; i<=n; ++i) {int temp = -que.top(); que.pop(); ; que.push(-(temp+arr[i]));}
for(int i=1, temp=sum=0; i<=m; ++i) {sum-=que.top(); brr[i]=-que.top(); que.pop();}
sum /= double(m); tempans = 0;
for(int i=1; i<=m; ++i) {tempans += (sum-brr[i])*(sum-brr[i]);} tempans = tempans / double(m);
ans = min(ans, tempans);return sqrt(tempans);
}
void simulate_anneal() {
for(double t=1e4, now=calc(); t>1e-4; t*=0.99, now=calc()) {
int a = rand()%n+1, b = rand()%n+1; swap(arr[a], arr[b]); double dt = calc()-now;
if(calc()>now||exp(dt/t) > double(rand())/RAND_MAX) swap(arr[a], arr[b]);
}
}
signed main() {
scanf("%lld%lld", &n, &m); for(int i=1, temp=ans=inf; i<=n; ++i) scanf("%lld", arr+i);
while(double(clock())/CLOCKS_PER_SEC < 0.95) simulate_anneal();
printf("%.2lf", sqrt(ans));
return 0;
}
后来的
#include<bits/stdc++.h>
#define int long long
#define inf 1e9
using namespace std;
int arr[22], brr[22], n, m; double sum, tempans, ans;
double calc() {
priority_queue<int> que;
for(int i=1; i<=m; ++i) que.push(0);
for(int i=1; i<=n; ++i) {int temp = -que.top(); que.pop(); ; que.push(-(temp+arr[i]));}
for(int i=1, temp=sum=0; i<=m; ++i) {sum-=que.top(); brr[i]=-que.top(); que.pop();}
sum /= double(m); tempans = 0;
for(int i=1; i<=m; ++i) {tempans += (sum-brr[i])*(sum-brr[i]);} tempans = tempans / double(m);
ans = min(ans, tempans);return sqrt(tempans);
}
void simulate_anneal() {
for(double t=1e4, now=calc(); t>1e-4; t*=0.99, now=calc()) {
int a = rand()%n+1, b = rand()%n+1; swap(arr[a], arr[b]); double dt = calc()-now;
if(calc()>now||exp(dt/t) > double(rand())/RAND_MAX) swap(arr[a], arr[b]);
}
}
signed main() {
scanf("%lld%lld", &n, &m); for(int i=1, temp=ans=inf; i<=n; ++i) scanf("%lld", arr+i);
sort(arr+1,arr+1+n);reverse(arr+1,arr+1+n);
while(double(clock())/CLOCKS_PER_SEC < 0.95) simulate_anneal();
printf("%.2lf", sqrt(ans));
return 0;
}