首页 > 代码库 > codeforce447 D SGU 548 贪心+优先队列
codeforce447 D SGU 548 贪心+优先队列
codeforce447 D - DZY Loves Modification
题意:
有一个n*m的矩阵,每次可以选择一行或者一列,可以得到这行或这列的所有元素sum的积分,
然后使这一列/行的每一个元素都减少p,接着再选择一行或一列,共操作k次,n,m<=1000,k<=1000000
求最多能得到多少积分
思路:
每次选择sum最大的行或者列,但是时间复杂度太大,过不去~
若选择一行,则每个列的sum一定减少p,同理;
若选择的行数和列数确定下来了,选择i行,k-i列,那么行和列之间谁选选择就没有影响;
因为在选择行的时候,每一列都的sum都减少p,每一列的相对大小没有变化,前k-i大的列还是那几列,同列。
所以可以用优先队列O(n)预处理出row_sum[i]和col_sum[k-i]的值。选i行则消耗了每列的i*p的大小,共k-i列,故共消耗了i*(k-i)*p,答案为
max( row_sum[i], col_sum[k-i])- i*(k-i)*p
注意:!!!!!WA了很久T.T,因为i*(k-i)*p会超过int范围!!!
1 /*=============================================================== 2 * Copyright (C) 2014 All rights reserved. 3 * 4 * File Name: codeforces447_D_greedy.cpp 5 * Author:sunshine 6 * Created Time: 2014年07月23日 7 * 8 ================================================================*/ 9 #include <map>10 #include <queue>11 #include <stack>12 #include <math.h>13 #include <stdio.h>14 #include <string.h>15 #include <iostream>16 #include <algorithm>17 18 using namespace std;19 20 int arr[1001][1001];21 long long row_sum[1000001];22 long long col_sum[1000001];23 24 int main(){25 int n,m,k,p;26 cin >> n >> m >> k >> p;27 28 priority_queue<int>row,col;29 30 for(int i = 0;i < n;i ++){31 long long tmp = 0;32 for(int j = 0;j < m;j ++){33 cin >> arr[i][j];34 tmp += arr[i][j];35 }36 row.push(tmp);37 }38 39 for(int j = 0;j < m;j ++){40 long long tmp = 0;41 for(int i = 0;i < n;i ++){42 tmp += arr[i][j];43 }44 col.push(tmp);45 }46 47 row_sum[0] = 0;48 for(int i = 1;i <= k;i ++){49 row_sum[i] = row_sum[i - 1] + row.top();50 row.push(row.top() - m * p);51 row.pop();52 }53 54 col_sum[0] = 0;55 for(int i = 1;i <= k;i ++){56 col_sum[i] = col_sum[i-1] + col.top();57 col.push(col.top() - n * p);58 col.pop();59 }60 61 long long res = row_sum[0] + col_sum[k];62 for(int i = 1;i <= k;i ++){63 res = max(res, row_sum[i] + col_sum[k - i] - (long long)i * (k - i) * p);64 }65 cout << res << endl;66 return 0;67 }
SGU 548 Dragons and Princesses
题意:
唐僧从起点1出发,依次从1到2到3……到n,第n位一定是一位公主,在2~n-1中可能是公主,也可能是龙,
d表示龙,p表示公主,每只龙有di个金币,每位公主有pi的美丽值,杀死一只龙就可以得到相应的财富值。
唐僧喜欢位置为n的那位公主,所以要和位置为n的公主结婚,所以他不能被其他公主喜欢上,必须被最后一个公主喜欢。
他被公主喜欢上的条件是:在遇到位置为i的公主是,如果pi小于等于唐僧杀死的龙的数量,那么公主
就认为唐僧很V5,会喜欢上唐僧,问题,唐僧成功和位置为n的公主结婚的情况下,最多能得到多少金币。
如果不能结婚,输出-1。
思路:
利用优先队列遇到龙就吃掉,遇到公主,发现吃多了,就把多余的小的都吐出来,当然遇到最后一个公主的时候不需要吐出来。
1 #include <stdio.h> 2 #include <iostream> 3 #include <queue> 4 #include <algorithm> 5 6 using namespace std; 7 8 struct node{ 9 int key;10 int id;11 friend bool operator < (node a,node b){12 return a.key > b.key;13 }14 }dro;15 16 int arr[200005];17 18 int main(){19 int n;20 char ch[10];21 int key;22 int base;23 while(scanf("%d", &n) != EOF){24 25 priority_queue<node>que;26 27 for(int i = 0;i < n - 1;i ++){28 scanf("%s %d", ch, &key);29 30 if(ch[0] == ‘d‘){31 dro.key = key;32 dro.id = i + 2;33 que.push(dro);34 }35 if(ch[0] == ‘p‘){36 if(i != n - 2){37 while(que.size() >= key){38 que.pop();39 }40 }else{41 base = key;42 }43 }44 }45 46 47 if(que.size() < base){48 puts("-1");49 }else{50 int res = 0;51 int top = 0;52 while(que.size()){53 dro = que.top();54 que.pop();55 // printf("key:%d id:%d\n",dro.key,dro.id);56 res += dro.key;57 arr[top++] = dro.id;58 }59 60 sort(arr,arr + top);61 62 printf("%d\n%d\n",res,top);63 64 for(int i = 0;i < top - 1;i ++){65 printf("%d ",arr[i]);66 }67 printf("%d\n",arr[top - 1]);68 }69 }70 return 0;71 }