[BZOJ 1029]建筑抢修
废了。
我彻底废了。
就一个贪心水体。按截止时间排序然后遍历，当前花时间能干完就干，不能的话看能不能把更劣的选择换。仅此而已。
代码：
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 | /************************************************************** Problem: 1029 User: danihao123 Language: C++ Result: Accepted Time:396 ms Memory:2764 kb****************************************************************/ #include <cstdio>#include <algorithm>#include <queue>using namespace std;typedef long long ll;#define REP(i,n) for(i=0;i<(n);i++)#define REP_B(i,n) for(i=1;i<=(n);i++)const int maxn=150001;struct Node{ int a,b; bool operator <(const Node& x) const{ return b<x.b; } bool operator >(const Node& x) const{ return b>x.b; }};Node T[maxn];priority_queue<ll> Q;int main(){ int n; register int i,ans=0; register ll cur=0; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&T[i].a,&T[i].b); sort(T+1,T+1+n); for(i=1;i<=n;i++){ if(cur+T[i].a<=T[i].b){ cur+=T[i].a; Q.push(T[i].a); }else{ if(Q.size() && Q.top()>T[i].a){ cur-=Q.top(); Q.pop(); cur+=T[i].a; Q.push(T[i].a); } } } printf("%d\n",Q.size()); return 0;} |
[POJ 2388]Who's in the Middle
这题题面长得挺吓人的（英文……），不过就是让你求中位数……
我怀疑会有卡快排的数据，不过我用的是STL的sort（sort好像用的不是普通的快排）
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #include <cstdio>#include <algorithm>using namespace std;const int maxn=10000;int A[maxn];int main(){ register int i; int n; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&A[i]); sort(A,A+n); printf("%d\n",A[n>>1]); return 0;} |
