2017美图点评编程题

第一题

求 子序列中为K的倍数的最长子序列长度，具体描述如下：

代码如下，100%通过率

#include <iostream> #include <string> #include <sstream> #include <vector> using namespace std; int main() { int N = 0; while (cin >> N) { vector<int > a(N, 0); for (int i = 0 ; i < N ; i++) { cin >> a[i]; } int K = 0; cin >> K; if (0 == N || 0 == K) { printf("0\n"); continue; } int out = 0; vector<int > tmp(N, 0); tmp[0] = a[0]; if (tmp[0] % K == 0) out = 1; for (int i = 1; i < N ; i++) { tmp[i] = tmp[i - 1] + a[i]; if (tmp[i] % K == 0) out = i + 1; } if (out == N) { printf("%d\n", out); continue; } for (int cnt = 1; cnt < N ; cnt++) { for (int i = cnt + out - 1; i < N; i++) { tmp[i] = tmp[i] - a[cnt - 1]; if (tmp[i] >= cnt && tmp[i] % K == 0) { out = out < i + 1 - cnt ? i + 1 - cnt : out; } } } printf("%d\n", out); } return 0; }

第二题

分发卷子的，吓唬人的题，具体题目如下：

代码如下， 100%通过率：

#include <iostream> #include <string> #include <vector> #include <algorithm> #include <utility> #include <vector> #include <stack> #include <map> using namespace std; int main() { int N = 0; while (cin >> N) { //vector<int > a(N , 0); int max = 0; int sum = 0; for (int i = 0; i < N ; i++) { int tmp = 0; cin >> tmp; sum += tmp; max = tmp > max ? tmp : max; } sum -= max; if (sum < max) { printf("No\n"); } else { printf("Yes\n"); } } return 0; }