我在HackerEarth上解决了一个问题。
问题是：Phineas正在他的后院建造一座城堡以打动Isabella(很奇怪，不是吗?)。他已经把所有东西都送来了并准备好了。连地面层都已经完成了。现在是时候制作上部分了。这就是事情变得有趣的地方。由于Ferb在长时间刷栅栏后睡觉了(而你们帮了他, 不是吗!), Phineas必须自己做所有的工作。他擅长这个，他想让你操作迷你起重机来吊起石头。墙上的石头已经被切割好并准备好等待你把它们吊起来。
现在我们没有Ferb来操作迷你起重机，他是一个专家，我们必须尽快完成工作。我们知道了起重机的最大承载能力和每块石头的重量。由于这是一个迷你起重机，我们不能一次放置超过2个石头(任何可能的大小)，否则它会影响到起重机的平衡。我们需要找出在多少轮中我们可以把石头交给正在建造城堡的Phineas。
输入: 输入的第一行给出T，表示测试用例的数量。对于每个测试用例，第一行给出M，表示起重机的最大承载能力。接下来每个测试用例的下一行的第一个整数N表示石头的数量，后面跟着N个数字，指定了每块石头X的重量。
输出: 对于每个测试用例，输出操作起重机的最小轮数，以便吊起所有的石头。
约束:
1 <= T <= 50
1 <= M <= 1000
1 <= N <= 1000
示例输入
1
50
3 28 22 48
样例输出
2
解释
首先，28和22将一起被举起。其次，将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)。
- 这是一种暴力方法还是动态规划方法？
- 有没有比这更好的方法？