ARC073 ：Ball Coloring （球染色） UPC-2018山东冬令营 （贪心）

本文主要是介绍ARC073 ：Ball Coloring （球染色） UPC-2018山东冬令营 （贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

球染色

时间限制: 2 Sec   内存限制: 512 MB
提交: 66   解决: 22
[ 提交][ 状态][ 讨论版]

题目描述

输入

输出

样例输入

2

3 7

2 5

样例输出

2

提示

·思路

    起初只考虑到其中一个情况，   

（Rmax − Rmin) × (Bmax − Bmin)  

    情况一：     最大与最小不在一边

      假如 Rmin 是所有中最小的， Bmax 是所有中最大的。

      这样的话只需要让Rmax 尽可能小， Bmin 尽可能大

      操作便是 min(x,y)给R， max(x,y)给 B

      然后只能过一半数据。  遇到  

    1 2

    3 4   就GG 了  答案应该是 3   而不是 4

    情况二：  最大与最小的在一边：  

        这个情况下贪心 比较麻烦，  贪心的操作是   假设 最大最小都在 B 这边

        枚举 R，  把   x，y  互换  然后   维护 差值最小;  这样的操作目的是   在不破坏最大最小的

        之间  尽可能使 另一边差值 最小

    

·具体操作  可以利用  multiset 容器，自带排序，还可以存在相同值，  set 是单纯集合

 注意 反向迭代器  rbegin()   rend()  begin()  end()    是指针

   begin() 是最小元素， end()是最大元素的下一个

   rbegin() 是最大元素，rend()是最小元素的前一个

·代码实现：

#include <iostream>
#include <bits/stdc++.h>
#include <string.h>
#define mem(a,b) memset(a,b,sizeof(a))using namespace std;
const int MOD=1e9+7;
typedef long long ll;
const int MAXN=1e5+15;
const ll INF=0x3f3f3f3f;typedef pair<ll,ll>PA;inline ll qpow(ll x,ll n){ll res=1;for(;n;n>>=1){if(n&1)res=(res*x);x=(x*x);}return res;}
pair<ll,ll>P;
vector<PA> V;
multiset<ll>R,B;
int cmp(PA a,PA b)
{return a.first<b.first;
}
int main()
{int n;ll x,y;ll res2,ans;cin>>n;for(int i=1;i<=n;i++){cin>>x>>y;V.push_back(make_pair(min(x,y),max(x,y)));R.insert(min(x,y));B.insert(max(x,y));}ll maR=-INF,maB=-INF;ll miR=INF,miB=INF;int col_max=0,col_min=0;sort(V.begin(),V.end(),cmp);for(int i=0;i<V.size();i++){maR=max(V[i].first,maR);maB=max(V[i].second,maB);miR=min(V[i].first,miR);miB=min(V[i].second,miB);}ans=(maR-miR)*(maB-miB);//cout<<ans<<endl;for(int i=0;i<V.size();i++){R.erase(R.find(V[i].first));B.insert(V[i].first);//swapB.erase(B.find(V[i].second));R.insert(V[i].second);//cout<<( *R.rbegin()-*R.begin() )<<" "<<( *B.rbegin()-*B.begin())<<endl;ans= min (ans,( *R.rbegin()-*R.begin() )*( *B.rbegin()-*B.begin()) );}cout<<ans<<endl;return 0;
}

123

这篇关于ARC073 ：Ball Coloring （球染色） UPC-2018山东冬令营 （贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---