Class Division

C++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 second
 
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;
}
 
 
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 second
using 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;
}

详情