首页 > 代码库 > 2017-4-25-Train:Codeforces Round #311 (Div. 2)
2017-4-25-Train:Codeforces Round #311 (Div. 2)
A. Ilya and Diplomas(贪心)
Soon a school Olympiad in Informatics will be held in Berland, n schoolchildren will participate there.
At a meeting of the jury of the Olympiad it was decided that each of the n participants, depending on the results, will get a diploma of the first, second or third degree. Thus, each student will receive exactly one diploma.
They also decided that there must be given at least min1 and at most max1 diplomas of the first degree, at least min2 and at most max2diplomas of the second degree, and at least min3 and at most max3 diplomas of the third degree.
After some discussion it was decided to choose from all the options of distributing diplomas satisfying these limitations the one that maximizes the number of participants who receive diplomas of the first degree. Of all these options they select the one which maximizes the number of the participants who receive diplomas of the second degree. If there are multiple of these options, they select the option that maximizes the number of diplomas of the third degree.
Choosing the best option of distributing certificates was entrusted to Ilya, one of the best programmers of Berland. However, he found more important things to do, so it is your task now to choose the best option of distributing of diplomas, based on the described limitations.
It is guaranteed that the described limitations are such that there is a way to choose such an option of distributing diplomas that all nparticipants of the Olympiad will receive a diploma of some degree.
Input
The first line of the input contains a single integer n (3 ≤ n ≤ 3·106) — the number of schoolchildren who will participate in the Olympiad.
The next line of the input contains two integers min1 and max1 (1 ≤ min1 ≤ max1 ≤ 106) — the minimum and maximum limits on the number of diplomas of the first degree that can be distributed.
The third line of the input contains two integers min2 and max2 (1 ≤ min2 ≤ max2 ≤ 106) — the minimum and maximum limits on the number of diplomas of the second degree that can be distributed.
The next line of the input contains two integers min3 and max3 (1 ≤ min3 ≤ max3 ≤ 106) — the minimum and maximum limits on the number of diplomas of the third degree that can be distributed.
It is guaranteed that min1 + min2 + min3 ≤ n ≤ max1 + max2 + max3.
Output
In the first line of the output print three numbers, showing how many diplomas of the first, second and third degree will be given to students in the optimal variant of distributing diplomas.
The optimal variant of distributing diplomas is the one that maximizes the number of students who receive diplomas of the first degree. Of all the suitable options, the best one is the one which maximizes the number of participants who receive diplomas of the second degree. If there are several of these options, the best one is the one that maximizes the number of diplomas of the third degree.
Examples
input
6
1 5
2 6
3 7
output
1 2 3
input
10
1 2
1 3
1 5
output
2 3 5
input
6
1 3
2 2
2 2
output
2 2 2
Means:
有三种奖,每种奖有最多发多少最少法多少的限制,现在要给n个人颁奖,要求越高的奖发的越多越好,现在问你每种奖发多少
Solve:
贪心,优先一等奖发最多,再二等奖法最多,再三等奖发最多,发一等奖的时候,二三等奖都先发最少的,然后取一等与二三取最小中的最小
Code:
1 #pragma comment(linker, "/STACK:36777216") 2 3 #include <bits/stdc++.h> 4 using namespace std; 5 #define LSON id << 1 , l , mid 6 #define RSON id << 1 | 1 , mid + 1 , r 7 #define ROOT 1 , 1 , n 8 #define CLR(x , y) memset(x , y , sizeof(x)) 9 #define LOWBIT(x) x & (-x)10 #define FORN(i , a , n) for(int i = (a) ; i <= (n) ; ++i)11 #define FORP(i , n , a) for(int i = (n) ; i >= (a) ; --i)12 #define CASE(x) printf("Case %d: ", x)13 #define SFD(x) scanf("%lf" , &x)14 #define SFC(x) scanf(" %c" , &x)15 #define SFS(x) scanf(" %s" , x)16 #define SFI(x) scanf("%d" , &x)17 #define SFI64(x) scanf("%I64d" , &x)18 #define PFF(x) printf("%f" , x)19 #define PFD(x) printf("%lf" , x)20 #define PFI(x) printf("%d" , x)21 #define PFC(x) printf("%c" , x)22 #define PFS(x) printf("%s" , x)23 #define PFI64(x) printf("%I64d" , x)24 #define SPACE printf(" ")25 #define PUT puts("")26 #define LPUP(i , j , k) for(int i = j ; i <= k ; ++i)27 #define LPDW(i , j , k) for(int i = j ; i >= k ; --i)28 #define PB(x) push_back(x)29 #define ALL(A) A.begin(), A.end()30 #define SZ(A) int((A).size())31 #define LBD(A, x) (lower_bound(ALL(A), x) - A.begin())32 #define UBD(A, x) (upper_bound(ALL(A), x) - A.begin())33 #define LOCAL34 static const double PI = acos(-1.0);35 static const double EPS = 1e-8;36 static const int INF = 0X3fffffff;37 typedef __int64 LL;38 typedef double DB;39 template<class T> inline40 T read(T &x)41 {42 x = 0;43 int f = 1 ; char ch = getchar();44 while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -1; ch = getchar();}45 while (ch >= ‘0‘ && ch <= ‘9‘) {x = x * 10 + ch - ‘0‘; ch = getchar();}46 x *= f;47 }48 49 /************************Little Pea****************************/50 51 int mx[5];52 int mi[5];53 int ans[5];54 int n;55 int main()56 {57 #ifdef LOCAL58 //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin);59 #endif60 read(n);61 LPUP(i , 1 , 3)62 {63 read(mi[i]);64 read(mx[i]);65 }66 ans[1] = min(mx[1] , n - mi[2] - mi[3]);67 ans[2] = min(mx[2] , n - ans[1] - mi[3]);68 ans[3] = n - ans[1] - ans[2];69 LPUP(i , 1 , 3)70 {71 PFI(ans[i]);SPACE;72 }73 }
B. Pasha and Tea(贪心 + 思想)
Pasha decided to invite his friends to a tea party. For that occasion, he has a large teapot with the capacity of w milliliters and 2n tea cups, each cup is for one of Pasha‘s friends. The i-th cup can hold at most ai milliliters of water.
It turned out that among Pasha‘s friends there are exactly n boys and exactly n girls and all of them are going to come to the tea party. To please everyone, Pasha decided to pour the water for the tea as follows:
- Pasha can boil the teapot exactly once by pouring there at most w milliliters of water;
- Pasha pours the same amount of water to each girl;
- Pasha pours the same amount of water to each boy;
- if each girl gets x milliliters of water, then each boy gets 2x milliliters of water.
In the other words, each boy should get two times more water than each girl does.
Pasha is very kind and polite, so he wants to maximize the total amount of the water that he pours to his friends. Your task is to help him and determine the optimum distribution of cups between Pasha‘s friends.
Input
The first line of the input contains two integers, n and w (1 ≤ n ≤ 105, 1 ≤ w ≤ 109) — the number of Pasha‘s friends that are boys (equal to the number of Pasha‘s friends that are girls) and the capacity of Pasha‘s teapot in milliliters.
The second line of the input contains the sequence of integers ai (1 ≤ ai ≤ 109, 1 ≤ i ≤ 2n) — the capacities of Pasha‘s tea cups in milliliters.
Output
Print a single real number — the maximum total amount of water in milliliters that Pasha can pour to his friends without violating the given conditions. Your answer will be considered correct if its absolute or relative error doesn‘t exceed 10 - 6.
Examples
input
2 4
1 1 1 1
output
3
input
3 18
4 4 4 2 2 2
output
18
input
1 5
2 3
output
4.5
Note
Pasha also has candies that he is going to give to girls but that is another task...
Means:
给你N个杯子，每个杯子的最大容量已知，共有W的茶，分给n个女孩和n个男孩，要求：
①给每个女孩的量都要相同。
②给每个男孩的量都要相同。
③给每个女孩的量是每个男孩的量的1/2.
求最大倒多少茶
Solve:
注意,并不是他给出的数据中并没有区分男女,所以,我们贪心的取最小的n个为女生的杯子,剩下的为男生的杯子(很显然要这样贪心,因为男生要取女生两倍并且男生的每杯茶的质量要相等),因为男生跟男生要相等,女生跟女生要相等,所以女生最大可以有的质量肯定是杯子最小的那个人的,男生也是同理,又因为男生是女生的两倍,所以如果女生最小杯子的两倍大于男生最小杯子,那么男生最多能倒的就是男生最小杯子的数量,而茶的最多能倒的总质量的公式又是男生最多能倒的x乘以男生的杯子数,加上女生每人能倒的也就是男生单位数量的一半,所以总的就是:1.5*n*x,但是如果总的能倒的超过总w,那么最大的肯定是w
Code:
1 #pragma comment(linker, "/STACK:36777216") 2 3 #include <bits/stdc++.h> 4 using namespace std; 5 #define LSON id << 1 , l , mid 6 #define RSON id << 1 | 1 , mid + 1 , r 7 #define ROOT 1 , 1 , n 8 #define CLR(x , y) memset(x , y , sizeof(x)) 9 #define LOWBIT(x) x & (-x)10 #define FORN(i , a , n) for(int i = (a) ; i <= (n) ; ++i)11 #define FORP(i , n , a) for(int i = (n) ; i >= (a) ; --i)12 #define CASE(x) printf("Case %d: ", x)13 #define SFD(x) scanf("%lf" , &x)14 #define SFC(x) scanf(" %c" , &x)15 #define SFS(x) scanf(" %s" , x)16 #define SFI(x) scanf("%d" , &x)17 #define SFI64(x) scanf("%I64d" , &x)18 #define PFF(x) printf("%f" , x)19 #define PFD(x) printf("%lf" , x)20 #define PFI(x) printf("%d" , x)21 #define PFC(x) printf("%c" , x)22 #define PFS(x) printf("%s" , x)23 #define PFI64(x) printf("%I64d" , x)24 #define SPACE printf(" ")25 #define PUT puts("")26 #define LPUP(i , j , k) for(int i = j ; i <= k ; ++i)27 #define LPDW(i , j , k) for(int i = j ; i >= k ; --i)28 #define PB(x) push_back(x)29 #define ALL(A) A.begin(), A.end()30 #define SZ(A) int((A).size())31 #define LBD(A, x) (lower_bound(ALL(A), x) - A.begin())32 #define UBD(A, x) (upper_bound(ALL(A), x) - A.begin())33 #define LOCAL34 static const double PI = acos(-1.0);35 static const double EPS = 1e-6;36 static const int INF = 0X3fffffff;37 typedef __int64 LL;38 typedef double DB;39 template<class T> inline40 T read(T &x)41 {42 x = 0;43 int f = 1 ; char ch = getchar();44 while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -1; ch = getchar();}45 while (ch >= ‘0‘ && ch <= ‘9‘) {x = x * 10 + ch - ‘0‘; ch = getchar();}46 x *= f;47 }48 49 /************************Little Pea****************************/50 static const int MAXN = 2e5 + 10;51 int n , w;52 int data[MAXN];53 int main()54 {55 #ifdef LOCAL56 //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin);57 #endif58 read(n);read(w);59 int ac = n << 1;60 LPUP(i , 1 , ac)61 {62 read(data[i]);63 }64 sort(data + 1 , data + 1 + ac);65 int mi = data[1] << 1 <= data[n + 1] ? data[1] << 1 : data[n + 1];66 if((DB)w - 1.5 * (DB)n * (DB)mi > EPS)67 {68 PFF(1.5 * (DB)n * (DB)mi);69 }70 else71 PFI(w);72 }
C. Arthur and Table(贪心 + 枚举 + 预处理 + 前缀和 QWQ)
Arthur has bought a beautiful big table into his new flat. When he came home, Arthur noticed that the new table is unstable.
In total the table Arthur bought has n legs, the length of the i-th leg is li.
Arthur decided to make the table stable and remove some legs. For each of them Arthur determined number di — the amount of energy that he spends to remove the i-th leg.
A table with k legs is assumed to be stable if there are more than half legs of the maximum length. For example, to make a table with 5legs stable, you need to make sure it has at least three (out of these five) legs of the maximum length. Also, a table with one leg is always stable and a table with two legs is stable if and only if they have the same lengths.
Your task is to help Arthur and count the minimum number of energy units Arthur should spend on making the table stable.
Input
The first line of the input contains integer n (1 ≤ n ≤ 105) — the initial number of legs in the table Arthur bought.
The second line of the input contains a sequence of n integers li (1 ≤ li ≤ 105), where li is equal to the length of the i-th leg of the table.
The third line of the input contains a sequence of n integers di (1 ≤ di ≤ 200), where di is the number of energy units that Arthur spends on removing the i-th leg off the table.
Output
Print a single integer — the minimum number of energy units that Arthur needs to spend in order to make the table stable.
Examples
input
2
1 5
3 2
output
2
input
3
2 4 4
1 1 1
output
0
input
6
2 2 1 1 3 3
4 3 5 5 2 1
output
8
Means:
神题。。。就是给你一张桌子,有n条腿,你可以锯掉多条腿,使得剩下的长度最长的腿的数量大于总数量的一半
Solve:
只要枚举桌子腿的最高高度,那么我们另最高高度为H,显然大于H的直接锯掉,把大于H的花费加到计数器,然后另小于H的有y个,H有x个,那么有等式,(最高的大于一半嘛),y-x>0所以必须去掉max(y-x+1 , 0)个,然后我们可以预处理出每个大于当前高度的花费,然后每次贪心锯小的的时候,贪心的枚举花费
Code:
1 #pragma comment(linker, "/STACK:36777216") 2 3 #include <bits/stdc++.h> 4 using namespace std; 5 #define LSON id << 1 , l , mid 6 #define RSON id << 1 | 1 , mid + 1 , r 7 #define ROOT 1 , 1 , n 8 #define CLR(x , y) memset(x , y , sizeof(x)) 9 #define LOWBIT(x) x & (-x) 10 #define FORN(i , a , n) for(int i = (a) ; i <= (n) ; ++i) 11 #define FORP(i , n , a) for(int i = (n) ; i >= (a) ; --i) 12 #define CASE(x) printf("Case %d: ", x) 13 #define SFD(x) scanf("%lf" , &x) 14 #define SFC(x) scanf(" %c" , &x) 15 #define SFS(x) scanf(" %s" , x) 16 #define SFI(x) scanf("%d" , &x) 17 #define SFI64(x) scanf("%I64d" , &x) 18 #define PFF(x) printf("%f" , x) 19 #define PFD(x) printf("%lf" , x) 20 #define PFI(x) printf("%d" , x) 21 #define PFC(x) printf("%c" , x) 22 #define PFS(x) printf("%s" , x) 23 #define PFI64(x) printf("%I64d" , x) 24 #define SPACE printf(" ") 25 #define PUT puts("") 26 #define LPUP(i , j , k) for(int i = j ; i <= k ; ++i) 27 #define LPDW(i , j , k) for(int i = j ; i >= k ; --i) 28 #define PB(x) push_back(x) 29 #define ALL(A) A.begin(), A.end() 30 #define SZ(A) int((A).size()) 31 #define LBD(A, x) (lower_bound(ALL(A), x) - A.begin()) 32 #define UBD(A, x) (upper_bound(ALL(A), x) - A.begin()) 33 #define LOCAL 34 static const double PI = acos(-1.0); 35 static const double EPS = 1e-6; 36 static const int INF = 0X3fffffff; 37 typedef __int64 LL; 38 typedef double DB; 39 template<class T> inline 40 T read(T &x) 41 { 42 x = 0; 43 int f = 1 ; char ch = getchar(); 44 while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -1; ch = getchar();} 45 while (ch >= ‘0‘ && ch <= ‘9‘) {x = x * 10 + ch - ‘0‘; ch = getchar();} 46 x *= f; 47 } 48 49 /************************Little Pea****************************/ 50 static const int MAXN = 1e5 + 10; 51 static const int OO = 0x3fffffff; 52 LL big[MAXN]; 53 LL num[MAXN]; 54 bool vis[MAXN]; 55 int n; 56 LL sum; 57 LL ans; 58 LL high[MAXN]; 59 LL cost[MAXN]; 60 LL have[MAXN]; 61 struct Node 62 { 63 LL l , c; 64 }data[MAXN]; 65 bool cmp(Node a , Node b) 66 { 67 return a.l < b.l; 68 } 69 int main() 70 { 71 #ifdef LOCAL 72 //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin); 73 #endif 74 read(n); 75 ans = OO; 76 LPUP(i , 0 , n - 1) 77 { 78 read(data[i].l); 79 ++num[data[i].l]; 80 } 81 LPUP(i , 0 , n - 1) 82 { 83 read(data[i].c); 84 } 85 sort(data , data + n , cmp); 86 LPDW(i , n - 1 , 1)///预处理高度花费 87 { 88 sum += data[i].c; 89 if(data[i].l != data[i - 1].l) 90 big[data[i - 1].l] = sum; 91 } 92 /*LPUP(i , 0 , n - 1) 93 { 94 PFI(big[data[i].l]);PUT; 95 }*/ 96 ans = big[data[0].l]; 97 ++cost[data[0].c]; 98 LPUP(i , 1 , n - 1) 99 {100 if(data[i].l != data[i - 1].l)101 {102 sum = big[data[i].l];103 LL tp = i - num[data[i].l] + 1;104 if(tp > 0)105 {106 LPUP(j , 1 , 200)107 {108 if(cost[j])109 {110 if(cost[j] >= tp)111 {112 sum += tp * j;113 tp = 0;114 break;115 }116 else117 {118 sum += cost[j] *j;119 tp -= cost[j];120 }121 }122 }123 }124 ans = min(sum , ans);125 }126 ++cost[data[i].c];127 }128 PFI64(ans);129 }
2017-4-25-Train:Codeforces Round #311 (Div. 2)