いくつかの欲張りな問題の問題解
35991 ワード
貪欲は気持ち悪いアルゴリズムであることはよく知られている.
従来のアルゴリズムやデータ構造とは異なり、貪欲な問題は一般的に考えられるのではなく、いくつかの推測や感性分析の下で、局所的に最適な案を見つけ、局所的な最適解を通じてグローバルな最適解を出す必要がある.
T 1:日焼け止め
C頭の乳牛が日光浴を行い、i頭目の乳牛はminSPF[i]からmaxSPF[i]の単位強度の間の日光を必要とする.
それぞれの乳牛は日光浴の前に必ず日焼け止めクリームを塗らなければならない.日焼け止めクリームにはL種類があり、i種類目を塗ると、体が受け取る日差しの強度はSPF[i]、i種類目の日焼け止めクリームにはcover[i]瓶がある.
最大でどれだけの乳牛を満たすことができることを求めて日光浴を行います.
入力フォーマット
1行目に整数CとLを入力します.
次のC行は、行ごとに牛のminSPFとmaxSPFの値、すなわちi行目にminSPF[i]とmaxSPF[i]を入力する.
さらに次のL行には、各行ごとに日焼け止めクリームのSPFとcover値、すなわちi行目にSPF[i]とcover[i]を入力する.
各行のデータ間はスペースで区切られています.
出力フォーマット
乳牛の日光浴を満たすことができる乳牛の数を表す整数を出力します.
データ範囲
1≤C,L≤25001≤C,L≤2500,1≤minSPF≤maxSPF≤10001≤minSPF≤maxSPF≤1000,1≤SPF≤10001≤SPF≤1000
サンプルを入力:
出力サンプル:
従来のアルゴリズムやデータ構造とは異なり、貪欲な問題は一般的に考えられるのではなく、いくつかの推測や感性分析の下で、局所的に最適な案を見つけ、局所的な最適解を通じてグローバルな最適解を出す必要がある.
T 1:日焼け止め
C頭の乳牛が日光浴を行い、i頭目の乳牛はminSPF[i]からmaxSPF[i]の単位強度の間の日光を必要とする.
それぞれの乳牛は日光浴の前に必ず日焼け止めクリームを塗らなければならない.日焼け止めクリームにはL種類があり、i種類目を塗ると、体が受け取る日差しの強度はSPF[i]、i種類目の日焼け止めクリームにはcover[i]瓶がある.
最大でどれだけの乳牛を満たすことができることを求めて日光浴を行います.
入力フォーマット
1行目に整数CとLを入力します.
次のC行は、行ごとに牛のminSPFとmaxSPFの値、すなわちi行目にminSPF[i]とmaxSPF[i]を入力する.
さらに次のL行には、各行ごとに日焼け止めクリームのSPFとcover値、すなわちi行目にSPF[i]とcover[i]を入力する.
各行のデータ間はスペースで区切られています.
出力フォーマット
乳牛の日光浴を満たすことができる乳牛の数を表す整数を出力します.
データ範囲
1≤C,L≤25001≤C,L≤2500,1≤minSPF≤maxSPF≤10001≤minSPF≤maxSPF≤1000,1≤SPF≤10001≤SPF≤1000
サンプルを入力:
3 2
3 10
2 5
1 5
6 2
4 1出力サンプル:
2
， ：
1. maxSPF 。
2. ， SPF 。
：
1. SPF ， 。
2. ， ， 。
3. ，4. a SPF ， ， SPF b a SPF 。
5. maxSPF 。
6. ， maxSPF ， maxSPF ， 。7. 。
：
#include
#include
#include
using namespace std;
const int N=2510;
typedef pair<int,int> PII;
PII cow[N],cover[N];
int C,L;
int main() {
cin>>C>>L;
for (int i=0;ii)
cin>>cow[i].first>>cow[i].second;
for (int i=0;ii)
cin>>cover[i].first>>cover[i].second;
sort(cow,cow+C);
int ans=0;
for (int i=C-1;i>=0;--i) {
int max_cover=0,p;
for (int j=0;jj)
if (cover[j].first>=cow[i].first&&cover[j].first<=cow[i].second&&max_cover<cover[j].first)
max_cover=cover[j].first,p=j;
if (max_cover!=0) {
ans++;
cover[p].second--;
if (cover[p].second==0) cover[p].first=0;
}
}
cout<<ans;
return 0;
}
T2.
N頭の牛が畜舎で草を食べている.
各畜舎は同じ時間帯に1頭の牛に草を食べさせるしかないので、複数の畜舎が必要になる可能性があります.
N頭の牛と1頭の牛が草を食べ始める時間Aと、草を食べ終わる時間Bが与えられ、1頭の牛は[A,B]の間ずっと草を食べている.
2頭の牛の草食区間が交差している場合(端点を含む)、この2頭の牛は同じ畜舎で草を食べるように手配できない.
必要な最小畜舎数と牛1頭当たりの畜舎案を求める.
入力フォーマット
1行目:整数Nを入力します.
2.N+1行目:i+1行目i頭牛の草食開始時間Aおよび草食終了時間Bを入力し、数の間をスペースで区切る.
出力フォーマット
1行目:必要な最小畜舎数を表す整数を入力します.
2.N+1行:i+1行目i頭牛が配置された畜舎番号を入力し、番号は1から、案が合法であればよい.
データ範囲
1≤N≤500001≤N≤50000,1≤A,B≤10000001≤A,B≤1000000
サンプルを入力:5
1 10
2 4
3 6
5 8
4 7
出力サンプル:4
1
2
3
2
4
， ：
1. A 。
2. ，
：
1. 。
2. >= 。
3. <= 。
4. 。
：
#include
#include
#include
#include
#include
using namespace std;
const int N=50010;
typedef pair<int,int> PII;
pairint> cow[N];
int n,mark[N];
int main() {
cin>>n;
for (int i=0;ii) {
cin>>cow[i].first.first>>cow[i].first.second;
cow[i].second=i;
}
sort(cow,cow+n);
priority_queue< PII,vector,greater > heap;
for (int i=0;ii)
if (heap.empty()||cow[i].first.first<=heap.top().first) {
PII stall=make_pair(cow[i].first.second,heap.size()+1);
heap.push(stall);
mark[cow[i].second]=stall.second;
}
else {
mark[cow[i].second]=heap.top().second;
PII stall=make_pair(cow[i].first.second,heap.top().second);
heap.pop();
heap.push(stall);
}
cout<endl;
for (int i=0;iendl;
return 0;
}
T3.
海岸は無限に長い直線で、陸地は海岸の片側に位置し、海洋は反対側に位置していると仮定します.
どの島も海側のある点に位置している.
レーダー装置はいずれも海岸線に位置し、レーダーの監視範囲はdであり、小島とあるレーダーとの距離がdを超えない場合、この小島はレーダーで覆われることができる.
デカルト座標系を用いて,海岸線をx軸,海の側をx軸上,陸地側をx軸下と定義した.
各小島の具体的な座標とレーダーの検出範囲を示し、すべての小島をレーダーで覆うために必要な最小レーダー数を求めてください.
入力フォーマット
第1行は、2つの整数nおよびdを入力し、それぞれ小島数およびレーダ検出範囲を表す.
次にn行、各行に2つの整数を入力し、それぞれ小島のx,y軸座標を表す.
同じ行のデータ間をスペースで区切ります.
出力フォーマット
必要な最小レーダー数を表す整数を出力し、解決策がなければ必要な数「-1」を出力します.
データ範囲
1≤n≤10001≤n≤1000
サンプルを入力:3 2
1 2
-3 1
2 1
出力サンプル:2
：
x 。
。
， i* i ， +1， 。
：
， 。
：
#include
#include
#include
#include
using namespace std;
typedef pair<double,double> PII;
const int N=1010;
PII len[N];
bool cmp(PII x,PII y) {
return x.second<y.second;
}
int main() {
int n;
double d;
cin>>n>>d;
for (int i=0;ii) {
cin>>len[i].first>>len[i].second;
int x=len[i].first,y=len[i].second;
if (y>d) {cout<1; return 0;}
len[i]=make_pair(x-sqrt(d*d-y*y),x+sqrt(d*d-y*y));
}
sort(len,len+n,cmp);
int ans=1;
double p=len[0].second;
for (int i=1;ii)
if (len[i].first>p) ++ans,p=len[i].second;
cout<<ans;
}
T4.
ちょうどH国の国慶節にあたり、王はn人の大臣を招待して賞のあるゲームをした.
まず、各大臣に左、右手にそれぞれ整数を書かせ、王自身も左、右手にそれぞれ整数を書かせた.
そして、このn人の大臣を一列に並べ、王は列の一番前に立った.
列を作った後、すべての大臣は国王の賞を受賞した金貨をいくつか獲得し、各大臣が獲得した金貨の数はそれぞれ:
この大臣の前に並んだ全員の左手の数の積を自分の右手の数で割って、下に整理した結果を取ります.
王はある大臣が特に多くの賞を受賞することを望んでいないので、チームの順序を再配置してもらいたいと思っています.賞を最も多く受賞した大臣は、できるだけ少ないようにしたいと思っています.
王の位置は常にチームの一番前にあることに注意してください.
入力フォーマット
最初の行には大臣の人数を表す整数nが含まれています.
2行目は2つの整数aとbを含み、間は1つのスペースで区切られ、国王の左手と右手の整数をそれぞれ表す.
次にn行、各行には2つの整数aとbが含まれ、間は1つのスペースで区切られ、各大臣の左手と右手の整数をそれぞれ表す.
出力フォーマット
出力は1行のみで、1つの整数を含み、並び替えたチームの中で最も賞をもらった大臣が獲得した金貨の数を表す.
データ範囲
1≤n≤10001≤n≤10000サンプルを入力:3
1 1
2 3
7 4
4 6
出力サンプル:2
：
（ i ）， ， i i-1 > i ， ， 。
x ， ：
（ ） 1～ x-1 x
x+1～ n x
， ， 。
， ， 。。。。
：
#include
#include
#include
#include
using namespace std;
const int N=1010;
typedef pair<int,int> PII;
PII member[N],sum[N];
int n;
vector<int> mul(vector<int> a,int b) {
vector<int> c;
int t=0;
for (int i=a.size()-1;i>=0;--i) {
t+=a[i]*b;
c.push_back(t%10);
t/=10;
}
while (t) {
c.push_back(t%10);
t/=10;
}
reverse(c.begin(),c.end());
return c;
}
vector<int> div(vector<int> a,int b) {
vector<int> c;
int t=0,s=0;
bool flag=false;
for (int i=0;ii) {
t=t*10+a[i];
s=t/b;
if (flag||s) {
flag=true;
c.push_back(s);
t%=b;
}
}
return c;
}
vector<int> get_max(vector<int> a,vector<int> b) {
if (a.size()>b.size()) return a;
if (a.size()return b;
if (a>b) return a;
return b;
}
void output(vector<int> a) {
for (int i=0;ii)
cout<<a[i];
return;
}
int main() {
cin>>n;
int x,y;
for (int i=0;i<=n;++i) {
cin>>x>>y;
member[i]=make_pair(x,y);
sum[i].first=x*y;
sum[i].second=x;
}
sort(sum+1,sum+n+1);
vector<int> res;
res.push_back(1);
vector<int> sum_max;
sum_max.push_back(0);
for (int i=0;i<=n;++i) {
if (i) sum_max=get_max(sum_max,div(res,sum[i].first/sum[i].second));
res=mul(res,sum[i].second);
}
output(sum_max);
return 0;
}
T5.
1つのツリーにはn個のノードがあり、これらのノードは1,2,3,...nとラベルされ、各ノードiには重みA[i]がある.
今この木の節点を全部染めます.染色のルールは:
ルートノードRはいつでも染色することができる.他のノードでは、染色される前に親ノードが色に染まっている必要があります.
各染色の代価はT*A[i]であり、Tは現在何回目の染色であるかを表す.
この木を染色する最小の総代価を求めます.
入力フォーマット
最初の行には、ツリーのノード数とルートノードのシーケンス番号を表す2つの整数nとRが含まれます.
2行目はn個の整数を含み、すべてのノードの重み値を表し、i番目の数はi番目のノードの重み値A[i]である.
次にn−1行、各行は2つの整数aとbを含み、2つのノードのシーケンス番号を表し、2つのノードは関係を満たす:aノードはbノードの親ノードである.
ルートノードを除く他のn−1ノードの親ノードとそれら自体がこのn−1行で表される.
同じ行の数をスペースで区切ります.
出力フォーマット
この木を染色する最小の総代価を表す整数を出力します.
データ範囲
1≤n≤10001≤n≤1000,1≤A[i]≤10001≤A[i]≤1000
サンプルを入力:5 1
1 2 1 2 4
1 2
1 3
2 4
3 5
0 0
出力サンプル:33
：
， ， “ ” ， 。
， ， 。
， ， ， ， 。 ， 。
， ， ， 。
， ， ， 。 。
， ， ， ， 。
：
#include
#include
using namespace std;
typedef long long LL;
const int N=1010;
struct Node{
int sum,father,size;
double ave;
}leaf[N];
LL ans;
int n,R;
int get_max() {
int p=0;
double leaf_max=0;
for (int i=1;i<=n;++i)
if ((leaf[i].ave>leaf_max)&&(i!=R)) leaf_max=leaf[i].ave,p=i;
return p;
}
int main() {
cin>>n>>R;
int x=0,y=0;
for (int i=1;i<=n;++i) {
cin>>x;
leaf[i].sum=x;
leaf[i].size=1;
leaf[i].ave=x;
ans+=leaf[i].sum;
}
for (int i=1;ii) {
cin>>x>>y;
leaf[y].father=x;
}
cin>>x>>y;
for (int i=1;ii) {
int p=get_max();
int fa=leaf[p].father;
ans+=leaf[p].sum*leaf[fa].size;
leaf[fa].sum+=leaf[p].sum;
leaf[fa].size+=leaf[p].size;
leaf[fa].ave=(double)leaf[fa].sum/leaf[fa].size;
for (int j=1;j<=n;++j)
if (leaf[j].father==p) leaf[j].father=leaf[p].father;
leaf[p].ave=-1;
}
cout<<ans;
}
T6.
整数を含む2次元行列が与えられ、サブ長方形は、アレイ全体にわたって任意のサイズ1*1以上の連続サブアレイである.
長方形の合計は、長方形内のすべての要素の合計です.
この問題では,最大和を持つサブ矩形を最大サブ矩形と呼ぶ.
たとえば、次の配列があります.0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
最大サブ長方形:9 2
-4 1
-1 8
最大15と最大15を持っています.
入力フォーマット
入力には、N*Nの整数配列が含まれます.
最初の行には、正方形の2次元配列のサイズを表す整数Nのみが入力されます.
2行目から、スペースと改行で区切られたN 2 N 2個の整数、すなわち2次元配列中のN 2 N 2個の要素を入力し、入力順は2次元配列の1行目から下へ逐行入力し、同じ行のデータは左から右へ逐行入力する.
配列内の数値は[-127127]の範囲内に保持されます.
出力フォーマット
最大サブ長方形の合計を表す整数を出力します.
データ範囲
1≤N≤1001≤N≤100
サンプルを入力:4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
出力サンプル:15
：
， ， ， O(n^4)， 。。。
， 。 O(n^3)。
：
#include
#include
using namespace std;
const int SIZE=110;
int a[SIZE][SIZE],s[SIZE][SIZE],n;
int main() {
cin>>n;
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j) {
cin>>a[i][j];
s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
int ans=-9999999,p=0;
for (int j=1;j<=n;++j)
for (int i=1;i<=j;++i) {
p=0;
for (int k=1;k<=n;++k) {
int q=s[j][k]+s[i-1][k-1]-s[i-1][k]-s[j][k-1];
if (p+q>=0) ans=max(ans,p+q),p+=q;
else ans=max(ans,p+q),p=0;
}
}
cout<<ans;
return 0;
}
T7.
今日ある会社はMつの任務を完成しなければならない.
各タスクには、対応する難易度レベルとタスクの完了に要する時間があります.
i番目のタスクの難易度レベルはyiyiで、タスクを完了するのにxixi分かかります.
企業がこのタスクを完了すると、(500*xi+2*yi)ドルの収入が得られます.
同社にはN台の機器があり、各機器には最長稼働時間とレベルがある.
タスクに要する時間がマシンの最長稼働時間を超えると、マシンはこのタスクを完了できません.
タスクの難易度がマシンのレベルを超えると、マシンは次のタスクを完了できません.
各機械は1日に1つの任務しか完成できない.
各任務は1台の機械でしか完成できない.
今日完了できるタスクの数を最大化できるように、タスク割り当てスキームを設計してください.
多くの解決策があれば、利益が最も高いものを選びたいと思っています.
入力フォーマット
いくつかのテスト例を入力します.
各試験例について、第1行は、機械数およびタスク数を表す2つの整数NおよびMを含む.
次のN行は、各行に2つの整数xi,yiを含み、それぞれマシンの最長稼働時間とマシンレベルを表す.
次にM行、各行には2つの整数xi,yiが含まれ、それぞれタスクの完了に要する時間とタスクの難易度レベルを表します.
出力フォーマット
各テスト・インスタンスについて、会社が今日完了できる最大タスク数と収益を表す2つの整数を出力します.
データ範囲
1≤N,M≤100000,00≤yi≤100
サンプルを入力:1 2
100 3
100 2
100 1
出力サンプル:1 50004
！！ 。。。。
。。。
： ，xi=1，yi=100， 500*1 100*2， ， “ ” “ ”。。。
，，， 。。。
：
#include
#include
#include
#include<set>
using namespace std;
const int SIZE=100010;
typedef long long LL;
typedef pair<int,int> PII;
PII mach[SIZE],task[SIZE];
int n,m;
LL ans,cnt;
int main() {
while (cin>>n>>m) {
for (int i=0;i>mach[i].first>>mach[i].second;
for (int i=0;i>task[i].first>>task[i].second;
sort(mach,mach+n);
sort(task,task+m);
multiset<int> ys;
for (int i=m-1,j=n-1;i>=0;--i) {
while (j>=0&&mach[j].first>=task[i].first)
ys.insert(mach[j--].second);
auto p=ys.lower_bound(task[i].second);
if (p!=ys.end()) {
cnt++;
ans+=task[i].first*500+task[i].second*2;
ys.erase(p);
}
}
cout<" "<endl;
}
return 0;
}
転載先:https://www.cnblogs.com/ABBEJ/p/11286149.html