题解 P1324 【矩形分割】

· · 题解

由于没有一次AC这道题，所以来发一篇题解。

思路

话说这道题标签已经把思路全部表示出来了。。。

问题在于怎么贪心。

样例实在是太水了，以至于怎么切得到的答案都是9。

推荐一组样例：

输入
4 2
4 5 6
1
输出
19

解释一下这组样例。图长这样：

如果先切横的，结果就是1+2*4+2*5+2*6=31。

如果先切竖的，结果就是4+5+6+1*4=19。

显然先切竖的更优。

由此，可以得出一个结论：先切代价大的。

于是，思路就出来了。先把两个数组从大到小排序，然后两个数组挨个比较，较大的就在答案上加上这个代价（要乘上切了多少刀），再把指针往后挪一位，直到全部算完即可。

细节

这道题细节还是蛮多的。（也就是我没有一次AC的原因）

1.是先取大的，不是先取小的。

2.注意是n-1和m-1，不能算成n和m。

3.最后的答案要开long long。

于是就可以愉快地AC了！

代码

相信所有人都会看这里吧（有没有干不好的事情我就不知道了），不过为了题解的完整性，我还是把代码附上——

（应该是史上最短）

#include<cstdio>
#include<algorithm>//用到sort
using namespace std;
const int MAXN=2020;//毕竟刚刚2020~
int a[MAXN],b[MAXN];//横线和竖线的代价
bool cmp(int aa,int bb){return aa>bb;}//从大到小
int main(){
    int n,m,s1=1,s2=1;//s1和s2可以是a数组和b数组的指针，也可以是横纵分成的块数
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++) scanf("%d",&a[i]);
    for(int i=1;i<m;i++) scanf("%d",&b[i]);
    sort(a+1,a+n,cmp);sort(b+1,b+m,cmp);//从大到小排序
    long long ans=0;//记录答案，注意long long
    for(int i=2;i<n+m;i++){//遍历
        if(a[s1]>b[s2]) ans+=s2*a[s1++];//选择大的，这里s2表示块数，s1指针后移一位
        else ans+=s1*b[s2++];//同理，和上面相反
    }
    printf("%lld",ans);
    return 0;//华丽结束
}

看我这么辛苦写一篇题解，总得点个赞再走呀~