import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
NC17497. Class Division
描述
输入描述
The first line contains a single integer n (1 ≤ n ≤ 250), denoting the number of students.
The next line contains n space-separated integers, s1, s2, ..., sn (1 ≤ si ≤ 106).
The next line contains a single integer m (1 ≤ m ≤ 30), denoting the number of classes.
The next m lines contains two space-separated integers each, li, ri, describing the i-th class.
It is guaranteed that the input is chosen such that there exist a way to assign all the students into classes.
输出描述
Print the only number — the answer for the problem. Your answer is considered correct if its absolute or relative error does not exceed 10-6.
Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if.
示例1
输入:
5 3 6 1 2 5 3 1 3 1 1 2 3
输出:
13.0000000000
说明:
The optimal strategy is to assign the students with scores 1, 2, 3 into the third class, assign the student with score 5 into the first class and assign the student with score 6 into the second class. Then, the scores of the classes areC++14(g++5.4) 解法, 执行用时: 821ms, 内存消耗: 608K, 提交时间: 2018-08-10 10:35:08
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 255;int a[N];double dp[35][N];pair<int, int> pi[N];#define x first#define y secondbool cmp(pair<int, int> a, pair<int, int> b) {if (a.y != b.y) return a.y < b.y;return a.x < b.x;}void update(double &x, double y) {x = max(x, y);}double get_random(int n, int m) {int c[35], sum[35], b[35];for (int i = 1; i <= m; i++) c[i] = i;random_shuffle(c + 1, c + m + 1);double ans = 0, pre = 0;for (int t = 1; t <= 2000000; t++) {int p = rand() % m + 1, q = rand() % m + 1;if (p == q) continue;if (p > q) swap(p, q);if (t % 20)swap(c[p], c[q]);else reverse(c + p + 1, c + q + 1);sum[m + 1] = 0;b[m + 1] = 0;for (int j = m; j >= 1; j--) {sum[j] = sum[j + 1] + pi[c[j]].y;b[j] = b[j + 1] + pi[c[j]].x;}double tmp = 0;int pos = 0;for (int i = 1; i <= m; i++) {int mi = b[i + 1], mx = sum[i + 1];/*mi <= n - pos - p <= mx*/int lt = max(pi[c[i]].x, -mx - pos + n);int rt = min(pi[c[i]].y, -mi - pos + n);while (lt > rt) cout << mi << " " << mx << " " << pi[c[i]].x << " " << pi[c[i]].y << " " << pos << " " << lt << " " << rt << endl;tmp += 1.0 * (a[pos + lt] - a[pos]) / lt;pos += lt;}ans = max(ans, tmp);if (tmp > pre) {pre = tmp;} else {if (t % 20) swap(c[p], c[q]);else reverse(c + p + 1, c + q + 1);}}return ans;}int main(){int n, m;while (scanf("%d", &n) != EOF) {for (int i = 1; i <= n; i++) scanf("%d", &a[i]);sort(a + 1, a + n + 1);reverse(a + 1, a + n + 1);for (int i = 2; i <= n; i++) a[i] += a[i- 1];scanf("%d", &m);for (int i = 1; i <= m; i++) scanf("%d%d", &pi[i].x, &pi[i].second);sort(pi + 1, pi + m + 1, cmp);for (int i = 0; i <= m; i++)for (int j = 0; j <= n; j++)dp[i][j] = -1e20;dp[0][0] = 0;for (int i = 0; i < m; i++)for (int j = 0; j <= n; j++) {if (dp[i][j] < -1e8) continue;for (int k = pi[i + 1].x; k <= pi[i + 1].y; k++) {if (j + k > n) continue;update(dp[i + 1][j + k], dp[i][j] + 1.0 * (a[j + k] - a[j]) / k);}}double ans = get_random(n, m);printf("%.20lf\n", max(ans, dp[m][n]));}return 0;}
C++ 解法, 执行用时: 464ms, 内存消耗: 500K, 提交时间: 2022-05-31 09:05:41
#include<bits/stdc++.h>#define x first#define y secondusing namespace std;const int N=255;int a[N];double dp[35][N];pair<int,int>pi[N];bool cmp(pair<int,int>a, pair<int,int>b){if (a.y!=b.y) return a.y<b.y;return a.x<b.x;}inline void update(double &x,double y){if(y>x) x=y;}double get_random(int n, int m){int c[35],sum[35],b[35];for (int i=1;i<=m;i++) c[i]=i;random_shuffle(c+1,c+m+1);double ans=0,pre=0;for(int t=1;t<=2000000;t++){int p=rand()%m+1,q=rand()%m+1;if(p==q) continue;if (p>q) swap(p,q);if(t%20) swap(c[p],c[q]);else reverse(c+p+1,c+q+1);sum[m+1]=0;b[m+1]=0;for(int j=m;j>=1;j--){sum[j]=sum[j+1]+pi[c[j]].y;b[j]=b[j+1]+pi[c[j]].x;}double tmp=0;int pos=0;for(int i=1;i<=m;i++){int mi=b[i+1],mx=sum[i+1];int lt=max(pi[c[i]].x,-mx-pos+n);int rt=min(pi[c[i]].y,-mi-pos+n);while (lt > rt) cout<<mi<<" "<<mx<<" "<<pi[c[i]].x<<" "<<pi[c[i]].y<<" "<<pos<<" "<<lt<<" "<<rt<<"\n";tmp+=1.0*(a[pos+lt]-a[pos])/lt;pos+=lt;}ans=max(ans,tmp);if(tmp>pre){pre=tmp;}else{if(t%20) swap(c[p],c[q]);else reverse(c+p+1,c+q+1);}}return ans;}signed main(){int n, m;while (scanf("%d", &n) != EOF) {for(int i=1;i<=n;i++) scanf("%d",&a[i]);sort(a+1,a+n+1);reverse(a+1,a+n+1);for(int i=2;i<=n;i++) a[i]+=a[i- 1];scanf("%d", &m);for(int i=1;i<=m;i++) scanf("%d%d",&pi[i].x,&pi[i].y);sort(pi+1,pi+m+1,cmp);for (int i=0;i<=m;i++)for (int j=0;j<=n;j++)dp[i][j]=-1e20;dp[0][0]=0;for(int i=0;i<m;i++)for(int j=0;j<=n;j++){if(dp[i][j]<-1e8) continue;for (int k=pi[i + 1].x;k<=pi[i + 1].y;k++){if(j+k>n) continue;update(dp[i+1][j+k],dp[i][j]+1.0*(a[j+k]-a[j])/k);}}double ans=get_random(n,m);printf("%.20lf\n", max(ans,dp[m][n]));}return 0;}