STL魚溜り釣り
1902 ワード
魚池釣り
時間制限:1000 ms メモリ制限:65536 KB
提出数:150 通過数:82
欲張りなやりかた
STL+ヒープ
dp
【テーマの説明】
N個の魚の池が一列に並んでいます.(N<100)各魚の池には一定の数の魚がいます.例えば、N=5の時は、次の表のようになります.
魚の池番号1分当たりの釣れる魚の数(1.1 000)は1分間当たりの釣り数の減少量(1.1 00)現在の魚の池から次の隣の魚の池までの所要時間(単位:分)1102321445320644593魚の池番号12345分当たりの釣れる魚の数(1.1.1000)101420169毎分当たりの釣り量の減少量(1.24653現在の魚の池から次の隣の魚の池までの所要時間(単位:分)3544
つまり、1番目の魚の池で釣りをして、1分目で10匹の魚が釣れます.2分目で8匹の魚しか釣れません.5分後にはもう魚が釣れません.1番目の魚の池から2番目の魚の池まで3分かかります.2番目の魚の池から3番目の魚の池まで5分かかります.
締め切りの時間T(T<1000)を提供して、釣りの方案を設計して、第1の魚の池から出発して、最も多い魚まで釣ることができることを望みます.
釣れた魚の数は釣りの回数だけ関係があり、釣りの時間は整数分です.
【入力】
全部で5行です.それぞれ表します.
第1行為N
第2行為の1分間に、それぞれの魚池で釣れる魚の数は、データの間に一マスで区切られます.
第3の行為は1分ごとにそれぞれの魚の池の釣りの数の減少量を過ぎて、すべてのデータの間は1スペースで仕切ります.
第4行為現在の魚の池は次の隣の魚の池まで必要な時間です.
第5行為の締切時間T.
一つの整数(231−1231−−−1−1を超えない)は、あなたのプランで一番多く釣れる魚を表します.
【入力例】
No.
コードの実装:
時間制限:1000 ms メモリ制限:65536 KB
提出数:150 通過数:82
欲張りなやりかた
STL+ヒープ
dp
【テーマの説明】
N個の魚の池が一列に並んでいます.(N<100)各魚の池には一定の数の魚がいます.例えば、N=5の時は、次の表のようになります.
魚の池番号1分当たりの釣れる魚の数(1.1 000)は1分間当たりの釣り数の減少量(1.1 00)現在の魚の池から次の隣の魚の池までの所要時間(単位:分)1102321445320644593魚の池番号12345分当たりの釣れる魚の数(1.1.1000)101420169毎分当たりの釣り量の減少量(1.24653現在の魚の池から次の隣の魚の池までの所要時間(単位:分)3544
つまり、1番目の魚の池で釣りをして、1分目で10匹の魚が釣れます.2分目で8匹の魚しか釣れません.5分後にはもう魚が釣れません.1番目の魚の池から2番目の魚の池まで3分かかります.2番目の魚の池から3番目の魚の池まで5分かかります.
締め切りの時間T(T<1000)を提供して、釣りの方案を設計して、第1の魚の池から出発して、最も多い魚まで釣ることができることを望みます.
釣れた魚の数は釣りの回数だけ関係があり、釣りの時間は整数分です.
【入力】
全部で5行です.それぞれ表します.
第1行為N
第2行為の1分間に、それぞれの魚池で釣れる魚の数は、データの間に一マスで区切られます.
第3の行為は1分ごとにそれぞれの魚の池の釣りの数の減少量を過ぎて、すべてのデータの間は1スペースで仕切ります.
第4行為現在の魚の池は次の隣の魚の池まで必要な時間です.
第5行為の締切時間T.
【出力】一つの整数(231−1231−−−1−1を超えない)は、あなたのプランで一番多く釣れる魚を表します.
【入力例】
5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14
【出力例】76
【出所】No.
コードの実装:
#include
using namespace std;
#define fish first
#define lake second
priority_queue >heap;//pair , ,
int main()
{
int n,f[101],d[101],t[101],tot;
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&f[i]);
for(int i=1;i<=n;i++)scanf("%d",&d[i]);
for(int i=1;i>tot;
int t1=0,maxx=0;
for(int k=1;k<=n;k++)//
{
int time=tot-t1;
int ans=0;
for(int i=1;i<=k;i++)
heap.push(make_pair(f[i],i));
while(time>0&&heap.top().fish>0)
{
paira=heap.top();
heap.pop();
ans+=a.fish;
a.fish-=d[a.lake];
heap.push(a);//
time--;
}
maxx=max(maxx,ans);
t1+=t[k];
}
cout<