250 Problem Statement
You have two favorite music bands. Each of them has just recorded a new album. You have bought both albums.
You know the durations (in seconds) of songs on each of the album. You are given these duration in vector <int>s durations1 and durations2. Elements of durations1 are the durations of songs on one of the album, elements of durations2 correspond to the songs of the other album.
You only have a limited amount of time before you have to leave for work. This amount of time is given in the int minutes. (Note that the durations are given in seconds while this time is given in minutes.) Given this time, you want to listen to as many different songs as possible. However, there is a constraint: as you are a fan of both bands, you have to listen to at least T different songs from each album.
Each song only counts if you listened to it from its beginning to its end. You can play the songs in any order you like. Selecting the next song to play and switching between albums takes zero time.
If the input data is such that it is impossible to listen to T different songs from each album in the time you have, return -1. Otherwise, return the largest number of different songs you can listen to.
Definition
Class: ListeningSongs
Method: listen
Parameters: vector <int>, vector <int>, int, int
Returns: int
Method signature: int listen(vector <int> durations1, vector <int> durations2, int minutes, int T)
(be sure your method is public)
题目类型：简单模拟+贪心
算法分析：先判断每个唱片是否能够听指定数目的歌曲(优先选择长度小的)，然后再从剩下的歌曲中优先选择长度小的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 |
// BEGIN CUT HERE // END CUT HERE #line 5 "ListeningSongs.cpp" #include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <stack> #include <fstream> #include <numeric> #include <iomanip> #include <bitset> #include <list> #include <stdexcept> #include <functional> #include <utility> #include <ctime> using namespace std; #define PB push_back #define MP make_pair #define LL long long #define ULL unsigned long long #define REP(i,n) for(i=0;i<(n);++i) #define FOR(i,l,h) for(i=(l);i<=(h);++i) #define FORD(i,h,l) for(i=(h);i>=(l);--i) typedef vector<int> VI; typedef vector<string> VS; typedef vector<double> VD; //typedef long long LL; typedef pair<int,int> PII; class ListeningSongs { public: int listen(vector <int> durations1, vector <int> durations2, int minutes, int T) { int tot = minutes * 60; sort (durations1.begin (), durations1.end ()); sort (durations2.begin (), durations2.end ()); int res, alla = 0, allb = 0; if (durations1.size () < T || durations2.size () < T) return -1; int posa = 0, posb = 0; for (int i = 0, j = 1; i < durations1.size () && j <= T; i++, j++) { alla += durations1[i]; posa++; } for (int i = 0, j = 1; i < durations2.size () && j <= T; i++, j++) { allb += durations2[i]; posb++; } if (alla + allb > tot) return -1; res = 2 * T; alla += allb; bool is_end = false; for (; posa < durations1.size () && posb < durations2.size (); ) { if (durations1[posa] < durations2[posb]) { if (alla + durations1[posa] <= tot) { alla += durations1[posa]; res++; posa++; } else { is_end = true; break; } } else { if (alla + durations2[posb] <= tot) { alla += durations2[posb]; res++; posb++; } else { is_end = true; break; } } } if (is_end) return res; for (; posa < durations1.size (); posa++) { if (alla + durations1[posa] <= tot) { alla += durations1[posa]; res++; } else break; } for (; posb < durations2.size (); posb++) { if (alla + durations2[posb] <= tot) { alla += durations2[posb]; res++; } else break; } return res; } // BEGIN CUT HERE public: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); if ((Case == -1) || (Case == 6)) test_case_6(); } private: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); } void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } } void test_case_0() { int Arr0[] = {300,200,100}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {400,500,600}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 17; int Arg3 = 1; int Arg4 = 4; verify_case(0, Arg4, listen(Arg0, Arg1, Arg2, Arg3)); } void test_case_1() { int Arr0[] = {300,200,100}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {400,500,600}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 10; int Arg3 = 1; int Arg4 = 2; verify_case(1, Arg4, listen(Arg0, Arg1, Arg2, Arg3)); } void test_case_2() { int Arr0[] = {60,60,60}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {60,60,60}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 5; int Arg3 = 2; int Arg4 = 5; verify_case(2, Arg4, listen(Arg0, Arg1, Arg2, Arg3)); } void test_case_3() { int Arr0[] = {120,120,120,120,120}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {60,60,60,60,60,60}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 10; int Arg3 = 3; int Arg4 = 7; verify_case(3, Arg4, listen(Arg0, Arg1, Arg2, Arg3)); } void test_case_4() { int Arr0[] = {196,147,201,106,239,332,165,130,205,221,248,108,60}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {280,164,206,95,81,383,96,255,260,244,60,313,101}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 60; int Arg3 = 3; int Arg4 = 22; verify_case(4, Arg4, listen(Arg0, Arg1, Arg2, Arg3)); } void test_case_5() { int Arr0[] = {100,200,300}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {100,200,300}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 2; int Arg3 = 1; int Arg4 = -1; verify_case(5, Arg4, listen(Arg0, Arg1, Arg2, Arg3)); } void test_case_6() { int Arr0[] = {100,200,300,400,500,600}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {100,200}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arg2 = 1000; int Arg3 = 3; int Arg4 = -1; verify_case(6, Arg4, listen(Arg0, Arg1, Arg2, Arg3)); } // END CUT HERE }; // BEGIN CUT HERE int main() { ListeningSongs ___test; ___test.run_test(-1); return 0; } // END CUT HERE |
500 Problem Statement
Some teams have competed in a programming contest. Each team has made one or more submissions. Each submission received some positive score. The total score of a team is the sum of the scores of all their submissions. The scoreboard is computed by sorting the teams according to their total scores. If multiple teams are tied, they are sorted lexicographically, with smaller names being higher in the scoreboard. The team on the top of the scoreboard is winning. (Only one team is winning at any moment, even if there are multiple teams tied for the winning total score.)
The scoreboard contains one line for each team. For each team, the line has the following format: "TeamName S1/T1 S2/T2 ... SN/TN". Here:
TeamName is the name of the team
N is the number of submissions they made
the values S1 through SN are the scores of those submissions
the values T1 through TN are times in minutes: submission Si was made after Ti minutes of the contest have elapsed
Different teams may have different numbers of submissions, worth a different number of points, and submitted at different times. The submissions are not necessarily ordered: neither by score, nor by submission time.
You are given a vector <string> scores: the scores of all teams, generated long after the contest was over. Each element of scores describes one team in the format shown above. The elements of scores are not necessarily ordered: neither by total score, nor by team name.
You would like to know who won the contest. However, this isn't necessarily the team that is currently winning. This is because it is possible that the scoreboard contains some submissions that happened after the end of the contest.
You know that the duration of the contest was an integer between 1 and 10^9, inclusive. Apart from that, you have no information about the exact duration. If the duration of the contest is D minutes, only the submissions that have Ti strictly smaller than D should be counted towards the correct total scores.
Given the content of scores, we say that a team could have won the contest if it was winning for some value of D from the above range. For each team, determine whether that team could have won the contest. Return a vector <int> with the same number of elements as scores. For each valid i, element i of the return value should be 1 if the team described by scores[i] could have won the contest, or 0 if it couldn't.
Definition
Class: ContestScoreboard
Method: findWinner
Parameters: vector <string>
Returns: vector <int>
Method signature: vector <int> findWinner(vector <string> scores)
(be sure your method is public)
题目类型：构造+枚举
算法分析：从正面考虑每个队是否能够赢其他队比较难想全，这里可以反面想。将所有队的提交按照时间递增排序，然后枚举时间，每次找比当前时间小的对应队的提交，将这个提交所具有的分数累加到对应队伍上。然后在这个时间下枚举所有队伍，找到分数最大或者是分数相同队名字典序最小的队伍，这个队伍一定可以赢(至少在这个时间下)，即将这个队伍的res置为1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
// BEGIN CUT HERE // END CUT HERE #line 5 "ContestScoreboard.cpp" #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; class ContestScoreboard { public: vector <int> findWinner(vector <string> scores) { vector <string> s = scores; int len = s.size (); vector <pair <string, vector <PII> > > team; team.resize (len); vector <int> time; vector <pair <int, PII> > event; for (int i = 0; i < len; i++) { stringstream ss (s[i]); ss >> team[i].first; while (ss) { char ch; PII tt; ss >> tt.first >> ch >> tt.second; team[i].second.push_back (tt); time.push_back (tt.second); event.push_back (pair <int, PII> (tt.second, PII (i, tt.first))); } } sort (time.begin (), time.end ()); time.erase (unique (time.begin (), time.end ()), time.end ()); sort (event.begin (), event.end ()); int eventlen = event.size (); int timelen = time.size (); vector <int> res, point; res.resize (len); point.resize (len); for (int i = 0, j = 0; i < timelen; i++) { for (; j < eventlen; j++) { if (event[j].first <= time[i]) point[event[j].second.first] += event[j].second.second; else break; } int pos = 0; for (int k = 0; k < len; k++) if (point[k] > point[pos] || (point[k] == point[pos] && team[k].first < team[pos].first)) pos = k; res[pos] = 1; } return res; } // BEGIN CUT HERE public: void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); } private: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); } void verify_case(int Case, const vector <int> &Expected, const vector <int> &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } } void test_case_0() { string Arr0[] = {"TVG 1/1 1/2 1/3", "AJI 1/4 1/5 1/6"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1, 1 }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(0, Arg1, findWinner(Arg0)); } void test_case_1() { string Arr0[] = {"GLP 1/114 1/195 1/171 1/19 1/146 1/29","BKPF 1/57 1/187 1/277 1/21 1/223 1/35"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1, 1 }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(1, Arg1, findWinner(Arg0)); } void test_case_2() { string Arr0[] = {"AAA 248/2 495/5 993/7","BBB 244/6 493/7 990/10", "CCC 248/2 495/5 993/10"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1, 0, 0 }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(2, Arg1, findWinner(Arg0)); } void test_case_3() { string Arr0[] = {"UBA 10/2 30/4 25/3 999/1000", "UNC 1/3 3/20 40/50", "UNLP 2/2 3/3 4/4 100/100", "UNR 999/1000000 999/999999", "UNS 999/100000000"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1, 0, 1, 1, 0 }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(3, Arg1, findWinner(Arg0)); } // END CUT HERE }; // BEGIN CUT HERE int main() { ContestScoreboard ___test; ___test.run_test(-1); return 0; } // END CUT HERE |
- « 上一篇：poj1113
- poj2007：下一篇 »