品牌网站建设渠道,网站地图提交地址,贵阳网站设计企业,商城微发布GYM101933I - Intergalactic Bidding 题解#xff1a;不考虑首先显然是个背包#xff0c;一开始直接用set模拟#xff0c;然后map存方案#xff0c;这样会mle。发现物品的体积有的特殊性 only one participant was allowed to make a bid at a time, each participant was … GYM101933I - Intergalactic Bidding 题解不考虑首先显然是个背包一开始直接用set模拟然后map存方案这样会mle。发现物品的体积有的特殊性 only one participant was allowed to make a bid at a time, each participant was only allowed to make one bid, and a participant making a bid had to bid at least twice the amount of the highest bid at the time. 于是直接对物品排序贪心取最大即可,因为对于种题目给定的s一定有唯一的方法组成。 #include bits/stdc.h
typedef long long ll;
const int N 1e3 7;
using namespace std;
struct Big {char x[1005]; int len;string s;bool operator (const Big A) const {if(A.len ! len) return 0;for(int i 0; i len; i) if(A.x[i] ! x[i]) return 0;return 1;}bool operator (const Big A) const {if(A.len ! len) return len A.len;for(int i len-1; i 0; --i) if(A.x[i] ! x[i]) return x[i] A.x[i];return 0;}Big operator (const Big A) const {Big ans *this;for(int i 0; i A.len; i) {ans.x[i] ans.x[i] A.x[i];}int mx max(A.len, len), f 0;for(int i 0; i mx1; i) {if(ans.x[i] 10) {ans.x[i]-10; ans.x[i1];}if(ans.x[i]) ans.len i1, f 1;}if(!f) ans.len 1;return ans;}Big operator - (const Big A) const {Big ans *this; int f 0;for(int i 0; i A.len; i) {ans.x[i] ans.x[i] - A.x[i];}int mx max(A.len, len);for(int i 0; i mx1; i) {if(ans.x[i] 0) {ans.x[i]10; --ans.x[i1];}if(ans.x[i]) ans.len i1, f 1;}if(!f) ans.len 1;return ans;}void read() {cin s; len s.size();for(int i 0; i len; i) x[len-i-1] s[i]-0;s.clear();}void write() {for(int i len-1; i 0; --i) printf(%d,x[i]); putchar(\n);}
} s, ZER;int n;
struct node{string nm; Big A;bool operator (const node a) const {return A a.A;}
} a[N];
vectorint ans;
int main() {ZER.x[0] 0; ZER.len 1;scanf(%d,n);s.read();for(int i 1; i n; i) {cin a[i].nm; a[i].A.read();}sort(a1,a1n);for(int i n ; i 1; --i) {if( a[i].A s || s a[i].A) {ans.push_back(i);s s - a[i].A;}}if(s ZER) {printf(%d\n,(int)ans.size());for(int i 0; i ans.size(); i) {cout a[ans[i]].nm \n;}}else puts(0);return 0;
}转载于:https://www.cnblogs.com/RRRR-wys/p/9817446.html
