解题思路

题目要求根据给定的正视图和右视图的高度信息，计算建造城镇所需的最少和最多积木数量，并判断是否存在可行解。关键在于：

​​正视图约束​​​​：

每列至少有一个塔的高度等于该列的正视图高度，其余塔的高度不超过该值。

​​​​右视图约束​​​​：

每行至少有一个塔的高度等于该行的右视图高度，其余塔的高度不超过该值。

每个位置 $(i,j)$的积木高度至少为 $min$(正视图列$i$高度,右视图行$j$高度)。

但为了满足正视图和右视图的全局约束，最少积木数应为：$∑$正视图各列高度$+$$∑$右视图各行高度$−$$∑$重叠部分，其中重叠部分需通过贪心策略匹配。

​​​​最多积木数​​​​：

每个位置 $(i,j)$的积木高度最多为 $min$(正视图列$i$高度,右视图行$j$高度)。

总和为所有位置取最大可能高度的累加。

​​​​可行性判断​​​​：

正视图和右视图的最大高度必须相等（即 $max$(正视图)==$max$(右视图)），否则无法同时满足两个视图的最高塔约束。

标程

/*
Code for poj 1736
By Pira 2011.7.22
*/
#include<cstdio>
#include<cstring>
using namespace std;
int i,j,k,l,num,ans1,ans2,m1,m2,a[5555],b[5555],c[5555];
int main()
{
    while(scanf("%d%d",&k,&l)!=-1)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        ans1=ans2=m1=m2=0;
        for(i=0;i<k;++i)
        {
            scanf("%d",&num);
            ++a[num];
            ans1+=num;
            ans2+=num*l;
            if(num>m1)m1=num;
        }
        for(i=5000;i>=0;--i)c[i]=c[i+1]+a[i+1],b[i]=b[i+1]+a[i+1]*(i+1);
        for(i=5000;i>=0;--i)b[i]=b[i]-c[i]*i;
        for(i=0;i<l;++i)
        {
            scanf("%d",&num);
            if(a[num])--a[num];
            else ans1+=num;
            ans2-=b[num];
            if(num>m2)m2=num;
        }
        if(m1==m2)printf("%d %d\n",ans1,ans2);
        else printf("No solution.\n");
    }
    return 0;
}