第一题，贪心。第一眼看到这个题目以为是经典背包问题，动态规划， 想了想不会做跳过了。做完后面三题回头看的时候发现题目条件比较特殊，用不着dp。ac
#include <iostream>
#include <vector>
using namespace std;
int solution(int target, vector<int>& cnt){
if(target == 0) return 0;
int ans = 0;
vector<int> val = {1, 5, 10, 50, 100};
for(int i=4; i>=0; --i){
int n = min(cnt[i], target/val[i]);
ans += n;
target -= val[i] * n;
if(target == 0)
return ans;
}
return -1;
}
int main(){
int n, t;
vector<int> cnt;
for(int i=0; i<5; ++i){
cin >> n;
cnt.push_back(n);
}
cin >> t;
cout<<solution(t, cnt)<<endl;
} 第二题，快排，每次选取最左侧元素作为枢纽元。ac 第三题，字母选数字的题，我考虑了类似输入“+-+--12-a5”输出-125的情况，直接ac了。负负得正。
第四题，正方形相交，没想到巧妙的办法，暴力判断四个顶点是否落在另一个正方形内，注意=也认为是相交的。ac
全部评论
(1) 回帖