D. Data Center
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/560/problem/B
Description
The startup "Booble" has shown explosive growth and now it needs a new data center with the capacity of m petabytes. Booble can buy servers, there are n servers available for purchase: they have equal price but different capacities. The i-th server can store ai petabytes of data. Also they have different energy consumption — some servers are low voltage and other servers are not.
Booble wants to buy the minimum number of servers with the total capacity of at least m petabytes. If there are many ways to do it Booble wants to choose a way to maximize the number of low voltage servers. Booble doesn't care about exact total capacity, the only requirement is to make it at least m petabytes.
Input
The first line contains two integer numbers n and m (1 ≤ n ≤ 2·105, 1 ≤ m ≤ 2·1015) — the number of servers and the required total capacity.
The following n lines describe the servers, one server per line. The i-th line contains two integers ai, li (1 ≤ ai ≤ 1010, 0 ≤ li ≤ 1), where ai is the capacity, li = 1 if server is low voltage and li = 0 in the opposite case.
It is guaranteed that the sum of all ai is at least m
Output
Print two integers r and w on the first line — the minimum number of servers needed to satisfy the capacity requirement and maximum number of low voltage servers that can be bought in an optimal r servers set.
Print on the second line r distinct integers between 1 and n — the indices of servers to buy. You may print the indices in any order. If there are many solutions, print any of them.
Sample Input
4 10
3 1
7 0
5 1
4 1
Sample Output
2 1
4 2
HINT
题意
有个人要买电池，要求买尽量少的电池，使得满足容量大于等于m，并且使得低能耗的电池尽量多
题解：
先排个序，判断出得至少买多少个电池
然后开始暴力枚举低能耗的电池个数，肯定优先拿电量大的，然后扫一遍就好了
代码
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define test freopen("test.txt","r",stdin) const int maxn=202501; #define mod 1000000007 #define eps 1e-9 const int inf=0x3f3f3f3f; const ll infll = 0x3f3f3f3f3f3f3f3fLL; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //************************************************************************************** struct node { ll x,y,z; }; bool cmp(node a,node b) { return a.x>b.x; } bool cmp1(node a,node b) { if(a.y==b.y) return a.x>b.x; return a.y>b.y; } node a[maxn]; ll sum1[maxn]; ll sum2[maxn]; int main() { int n=read(); ll m=read(); for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].z=i; sort(a+1,a+n+1,cmp); ll sum=0; int num=0; for(int i=1;i<=n;i++) { num=i; sum+=a[i].x; if(sum>=m) break; } sort(a+1,a+n+1,cmp1); int flag=0; for(int i=1;i<=n;i++) if(a[i].y!=1) { flag=i; break; } int num1=1,num2=1; if(flag==0) flag=n+1; for(int i=1;i<flag;i++) { sum1[num1]=sum1[num1-1]+a[i].x; num1++; } for(int i=flag;i<=n;i++) { sum2[num2]=sum2[num2-1]+a[i].x; num2++; } for(int i=num;i>=0;i--) { if(sum1[i]+sum2[num-i]>=m) { cout<<num<<" "<<i<<endl; for(int j=1;j<=i;j++) cout<<a[j].z<<" "; for(int j=flag;j<flag+num-i;j++) cout<<a[j].z<<" "; cout<<endl; return 0; } } }