Codeforces Round #100 D : New Year Contest
問題概要
解くのにA[i]分必要な問題がN(<100)問ある。問題iをt分で解いたらmax(0, t-360)だけのペナルティが与えられる。720分でどれだけの問題が解けるか求め、そのうち最小のペナルティを求める問題。
解法
簡単な順に解けば良い。証明というほどではないが、小さい方からとれるだけとった方がよいのは相当に自明。順番については、確かに易->難の順序を入れ替えても得することはないように思える(適当)。
acceptされた、ごちゃごちゃしたコード
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAX_T = 720; const int MAX_N = 100; const int INF = 1<<29; int N; int as[MAX_N]; int bs[MAX_N]; pair<int,int> dp[MAX_T + 1]; int penalty(int t, int start){ return max(0, t + start - 360); } void init(){ scanf("%d", &N); for(int i=0; i<N; i++){ scanf("%d", as + i); } } void solve_brute(){ sort(as, as + N); pair<int,int> maxi(0, 0); do{ int t = 10; pair<int,int> score(0, 0); for(int i=0; i<N; i++){ t += as[i]; if(t > 720){ break; } score.first++; score.second -= max(0, t - 360); } if(score > maxi){ maxi = score; memcpy(bs, as, sizeof(as)); } }while(next_permutation(as, as+N)); puts(""); printf("%d %d\n", maxi.first, -maxi.second); for(int i=0; i<maxi.first; i++){ printf("%d, ", bs[i]); }puts(""); sort(as, as+N); for(int i=0; i<maxi.first; i++){ printf("%d, ", as[i]); }puts(""); } void solve(){ sort(as, as + N); int t = 10, sol = 0, pen = 0; for(int i=0; i<N; i++){ t += as[i]; if(t > 720){ break; } sol++; pen += max(0, t - 360); } printf("%d %d\n", sol, pen); } int main(){ init(); solve_brute(); return 0; }