「CF529B」Group Photo 2(online mirror version)

2015年3月23日2,6380

Many years have passed, and n friends met at a party again. Technologies have leaped forward since the last meeting, cameras with timer appeared and now it is not obligatory for one of the friends to stand with a camera, and, thus, being absent on the photo.

Simply speaking, the process of photographing can be described as follows. Each friend occupies a rectangle of pixels on the photo: the i-th of them in a standing state occupies a w_i pixels wide and a h_i pixels high rectangle. But also, each person can lie down for the photo, and then he will occupy a h_i pixels wide and a w_i pixels high rectangle.

The total photo will have size W × H, where W is the total width of all the people rectangles, and H is the maximum of the heights. The friends want to determine what minimum area the group photo can they obtain if no more thann / 2 of them can lie on the ground (it would be strange if more than n / 2 gentlemen lie on the ground together, isn’t it?..)

Help them to achieve this goal.

Input

The first line contains integer n (1 ≤ n ≤ 1000) — the number of friends.

The next n lines have two integers w_i, h_i (1 ≤ w_i, h_i ≤ 1000) each, representing the size of the rectangle, corresponding to the i-th friend.

Output

Print a single integer equal to the minimum possible area of the photo containing all friends if no more than n / 2 of them can lie on the ground.

Sample test(s)

input

10 1

20 2

30 3

output

180

180

input

3 1

2 2

4 3

output

21

input

1
5 10

5 10

output

50

题解

枚举高贪心

#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define inf 1000000000
#define eps 1e-8
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,ans;
int w[1005],h[1005];
bool vis[1005];
priority_queue<int,vector<int> >q;
void solve(int x)
{
    while(!q.empty())q.pop();
    memset(vis,0,sizeof(vis));
    int lie=0,sum=0;
    for(int i=1;i<=n;i++)
        if(h[i]>x)
        {
            vis[i]=1;
            lie++;sum+=h[i];
            if(w[i]>x)return;
        }
    for(int i=1;i<=n;i++)
        if(!vis[i])
        {
            if(w[i]<=x)q.push(w[i]-h[i]);
            sum+=w[i];
        }
    while(lie<n/2&&!q.empty())
    {
        int t=q.top();q.pop();
        if(t>0)sum-=t,lie++;
        else break;
    }
    if(lie<=n/2)ans=min(ans,sum*x);
}
int main()
{
    ans=2000000000;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&w[i],&h[i]);
    for(int i=0;i<=1000;i++)
        solve(i);
    printf("%d\n",ans);
    return 0;
}

#include<cmath>

#include<queue>

#include<vector>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define inf 1000000000

#define eps 1e-8

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,ans;

int w[1005],h[1005];

bool vis[1005];

priority_queue<int,vector<int> >q;

void solve(int x)

{

while(!q.empty())q.pop();

memset(vis,0,sizeof(vis));

int lie=0,sum=0;

for(int i=1;i<=n;i++)

if(h[i]>x)

{

vis[i]=1;

lie++;sum+=h[i];

if(w[i]>x)return;

}

for(int i=1;i<=n;i++)

if(!vis[i])

{

if(w[i]<=x)q.push(w[i]-h[i]);

sum+=w[i];

}

while(lie<n/2&&!q.empty())

{

int t=q.top();q.pop();

if(t>0)sum-=t,lie++;

else break;

}

if(lie<=n/2)ans=min(ans,sum*x);

}

int main()

{

ans=2000000000;

scanf("%d",&n);

for(int i=1;i<=n;i++)

scanf("%d%d",&w[i],&h[i]);

for(int i=0;i<=1000;i++)

solve(i);

printf("%d\n",ans);

return 0;

}

« [JSOI2010] 旅行「BZOJ3850」ZCC Loves Codefires »

hzwer.com _ Home | http://hzwer.com

「CF529B」Group Photo 2(online mirror version)

分类目录

热门文章

Myfriends

近期评论