ZOJ 3194 Coverage(贪心)

题意:对于题目给的点,x固定,而与x组合的y可以任意交换,求如何安置y可使这些点组成线段下面的面积最大,最大面积是多少

分析:可以发现Xn-Xn-1的越大那么乘以y越大,所以我们只需求出,然后ΔX越大的数和y越大的数相乘在除以2就是结果,通过画图很容易得出结论

         但是还有一个问题就是,对于i=0,i=n-1,Yi只乘以了一遍,而对于0<i<n的区间,每个Yi都乘以了两遍

         所以在求ΔX时候,当i=0,ΔX=X1-X0,当i=n-1时,ΔX=Xn-1-Xn-2,而对于0<i<n,ΔX=Xi+1-xi-1;

         这样就能确保每个y每个都可以被乘以了两次。

         (对于两边的区间Y不仅被乘以了1次,而且是最小的两个值放在了两边)

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int MN=1100;
double x[MN],y[MN],r[MN];

bool cmp(double a,double b)
{
    return a<b;
}

int main()
{
    int i,j,n;
    double sum;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        sum=0;
        scanf("%d",&n);
        for(i=0;i<n;i++)
           scanf("%lf%lf",&x[i],&y[i]);
        sort(x,x+n,cmp);
        sort(y,y+n,cmp);
        for(i=0;i<n-1;i++)
        {
            if(i==0) r[i]=x[i+1]-x[i];
            else r[i]=x[i+1]-x[i-1];
        }
        r[i]=x[i]-x[i-1];
        sort(r,r+n,cmp);
        for(i=0;i<n;i++)
        {
            sum+=r[i]*y[i];
        }
        printf("%.1lf\n",sum/2);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏潇涧技术专栏

Problem: Longest Common Subsequence

最长公共子序列(LCS)是典型的动态规划问题,如果不理解动态规划请移步先看这篇动态规划的总结,否则本文中的代码实现会不理解的哟!

6710
来自专栏C/C++基础

Dijkstra算法求单源最短路径

在一个连通图中,从一个顶点到另一个顶点间可能存在多条路径,而每条路径的边数并不一定相同。如果是一个带权图,那么路径长度为路径上各边的权值的总和。两个顶点间路径长...

47610
来自专栏Petrichor的专栏

leetcode: 62. Unique Paths

12520
来自专栏程序生活

TensorFlow入门:MNIST数据的单层逻辑回归代码单层回归代码输出结果

22640
来自专栏数说工作室

【SAS Says】扩展篇:IML(2)

上一篇“高级篇:IML(1)”发出来之后,有朋友反映东西东西太简单了,根本不能算“高级”。想想也是,暂时还没有介绍太复杂的SAS程序,于是决定将本篇定为“扩展篇...

32860
来自专栏数据结构与算法

洛谷P2503 [HAOI2006]均分数据(模拟退火)

20700
来自专栏数据结构与算法

1099 字串变换 2002年NOIP全国联赛提高组

1099 字串变换 2002年NOIP全国联赛提高组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解 题目描述 D...

28030
来自专栏PPV课数据科学社区

【学习】K近邻算法基础:KD树的操作

Kd-树概念 Kd-树其实是K-dimension tree的缩写,是对数据点在k维空间中划分的一种数据结构。其实,Kd-树是一种平衡二叉树。 举一示例: 假设...

34050
来自专栏人工智能

Tensorflow下Char-RNN项目代码详解

前言 Char-RNN,字符级循环神经网络,出自于Andrej Karpathy写的The Unreasonable Effectiveness of Recu...

706100
来自专栏杨熹的专栏

用 LSTM 来做一个分类小问题

用一个简单的例子来看看 LSTM 在 tensorflow 里是如何做分类问题的。 这个例子特别简单,就是一个长度为 20 的二进制串,数出其中 1 的个数,简...

38480

扫码关注云+社区

领取腾讯云代金券