HackerEarthに関する質問を解決しました。質問は
フィニアスは裏庭にイザベラを感動させる城を建てています(奇妙ですね)。彼はすべてを配達して準備を整えました。1階も完成しました。今が上部を作る時です。ここで物事が面白くなります。ファーブがフェンスを塗って長い一日を過ごした後、家の中で眠っているので(そしてあなたたちが彼を助けました、そうしませんでした!)、フィニアスはすべての仕事を自分でしなければなりません。彼はこれが得意で、ミニクレーンを操作して石を持ち上げるだけです。壁の石はカットされており、持ち上げるのを待っています。
今では、彼が専門家であるミニクレーンを操作するためのファーブがいないので、できるだけ早く仕事をする必要があります。クレーンの最大吊り上げ能力と各石の重量が与えられます。ミニクレーンですので、一度に2個以上の石(任意のサイズ)を置くことはできません。そうしないと、クレーンのバランスが崩れます。城を建てているフィニアスに石を何ターンで届けることができるかを知る必要があります。
入力:入力の最初の行は、テストケースの数であるTを示します。各テストケースについて、最初の行はM、クレーンの最大持ち上げ能力を示します。各テストケースの次の行の最初の整数Nは石の数を示し、その後にN個の数が続き、個々の石Xの重量を指定します。
出力:各テストケースについて、すべての石を持ち上げるためにクレーンが操作される最小回転数を印刷します。
制約:
1 <= T <= 50
1 <= M <= 1000
1 <= N <= 1000
サンプル入力
1
50
3 28 22 48
サンプル出力
2
説明最初のターンでは、28と22が一緒に持ち上げられます。2番目のターンで48が持ち上げられます。クレーンの最大容量を超える重量の石を廃棄します。
今、私はこの質問を解決しました、そして私のソースコードは
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
int main(void) {
int T = 0;
scanf("%d",&T);
while(T--) {
int i = 0,M = 0, N = 0,max = 0, res = 0, index = 0, j = 0, temp = 0;
vector<int> v1;
scanf("%d",&M);
scanf("%d",&N);
for(i = 0; i < N ;++i) {
scanf("%d",&temp);
if(temp <= M)
v1.push_back(temp);
}
for(i = 0; i < v1.size() ; ++i) {
max = 0;
index = 0;
if(v1[i] != -1) {
for(j = i + 1; j < v1.size(); ++j) {
if(v1[j] != -1) {
temp = v1[i] + v1[j];
if(temp > max && temp <= M) {
max = temp;
index = j;
}
}
}
++res;
v1[i] = -1;
v1[index] = -1;
}
}
printf("%d\n",res);
}
return 0;
}
今ここに私の質問があります
これはナップザックプロブレムの簡易版です
ナップサック問題は典型的な動的計画法の質問ですが、この単純化された質問は動的計画法を必要としません。ソリューションの複雑さは確かにO(n ^ 2)です。このアプローチは、貪欲と表現する方が適しています。各石に最適なペアが存在する場合は、それを見つけようとしました。最初に石を並べ替えて、並べ替えられたベクトルで作業すると、複雑さをさらにO(nlgn)に減らすことができます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加