度小满笔试 64 100 0 求讨论
第一题：
思路是从后往前考虑怎么杀敌人，这样能保证每次杀的敌人都是最多的。
#include<iostream>
using namespace std;
int main(){
int n;
cin >> n;
int A[n + 1];
for (int i = 0; i < n; ++i)
cin >> A[i + 1];
int ans = 0;
int head = n;
while (head > 0){
if (head >= 3){
if ((head - 1) % 2 == 0){
ans += A[head];
A[head - 1] = A[head - 1] > A[head] ? A[head - 1] - A[head] : 0;
A[(head - 1) / 2] = A[(head - 1) / 2] > A[head] ? A[(head- 1) / 2] - A[head] : 0;
}
else{
ans += A[head];
A[head / 2] = A[head / 2] > A[head] ? A[head - 1] - A[head] : 0;
}
}
else if (head == 2){
ans += A[2];
A[1] = A[1] > A[2] ? A[1] - A[2] : 0;
}
else{
ans += A[1];
}
--head;
}
cout << ans << endl;
} 第二题用一个最小堆来记录在桥上的车，每次发现下一辆车可以上桥的时候，就加入堆，否则就把堆顶的车pop，即堆顶的车通过了桥，此时时间也往前走。 #include <queue>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;
int main(){
int N, W;
cin >> N >> W;
int w[N], t[N];
for (int i = 0; i < N; ++i)
cin >> w[i];
for (int i = 0; i < N; ++i)
cin >> t[i];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;
int cnt = 0;
int sum = 0;
int T = 0;
while (cnt < N){
if (sum + w[cnt] <= W){
Q.push(make_pair(T + t[cnt], w[cnt]));
sum += w[cnt];
++cnt;
}
else{
sum -= Q.top().second;
T = Q.top().first;
Q.pop();
}
}
while (!Q.empty()){
T = Q.top().first;
Q.pop();
}
cout << T << endl;
return 0;
} 
