absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] Codeforces 893F
[破碎的状态] cf 914D

[破碎的状态] ARC073E

absi2011 posted @ Nov 24, 2017 03:40:48 PM in 刷题记录 with tags 小高考 集训队作业 瞎搞 atcoder , 839 阅读

题意:

n个袋子,每个袋子里俩球

你要把一个染成红色,一个染成蓝色

每个球上面有个数字,求(蓝色球的极差)*(红色球的极差)的最小值

例如,蓝色为1,3,4,1,2,1,7 (极差:7-1=6)

红色为4,2,3,1,8,7,2 (极差:8-2=6)

则这一组分配方案为36

我们可以发现,最大的球一定会分到红蓝之一,我们假设是蓝色

最小的球,如果在红色:

则每一组,我们把大的给蓝色,小的给红色,肯定最优

如果我们把最大的给蓝色,最小的还给蓝色

那么我们把袋子排序,按较小的那个为关键字

这样,我们枚举前若干个袋子取较大的,后若干个取较小的

(因为 我们确定了 第1~x个取较大的 x+1为最小值 后面显然取更小的较优)

(如果1~x中,较大的比x+1的最小值还要小也同理)

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
    int x;
    int y;
    friend bool operator < (const node &a,const node &b)
    {
        return a.x<b.x;
    }
};
node c[200005];
int x[200005],y[200005];
const int inf=1000000007;
int mins[200005],maxs[200005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    int r_max=-1,b_max=-1;
    int r_min=inf,b_min=inf;
    for (i=0;i<n;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        if (x[i]>y[i]) swap(x[i],y[i]);
        c[i].x=x[i];
        c[i].y=y[i];
        r_max=max(r_max,x[i]);
        b_max=max(b_max,y[i]);
        r_min=min(r_min,x[i]);
        b_min=min(b_min,y[i]);
    }
    long long ans1=(long long)(r_max-r_min)*(b_max-b_min);
    //B can be chosen randomly now!
    b_min=r_min;
    sort(c,c+n);
    int ans=inf;
    for (i=0;i<n;i++)
    {
        mins[i]=c[i].y;
        maxs[i]=c[i].y;
        if (i>0) mins[i]=min(mins[i-1],c[i].y);
        if (i>0) maxs[i]=max(maxs[i-1],c[i].y);
        if (i!=n-1)
        {
            ans=min(ans,max(maxs[i],c[n-1].x)-min(mins[i],c[i+1].x));
        }
        else
        {
            ans=min(ans,maxs[i]-mins[i]);
        }
    }
    cout<<min((long long)ans*(b_max-b_min),ans1)<<endl;
    return 0;
} 
pavzi.com 说:
Jan 08, 2024 06:32:29 PM

Pavzi.com provides all the news about Gadgets, the Economy, Technology, Business, Finance and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. pavzi.com Our site is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter