CodeForces 3B Lorry 贪心

题目大意是有体积为v的背包，有体积为1和2的两种物品若干，这些物品都有各自的价值。求如何取这些物品可使背包中物品的价值最大。

开始一看到是背包就傻眼了==因为数据量太大1 ≤ n ≤ 10⁵; 1 ≤ v ≤ 10⁹ 

搜题解有说用优先队列做的，好麻烦==有一种思路我很喜欢：既然涉及到背包或者贪心这类DP问题，一定是取最优的解。即如果把两种船只分别存到两个数组里，再由大到小排序，最终的结果一定是两个数组各自的前1~M个，且无跳跃，分别都是连续的。那么假设我遍历大船的情况从0到船只数，意味着分别是有0个大船、1个大船、、、所有大船，剩余的费用给小船。在循环中记录每次的最大值及大船、小船的个数。

还有就是最后输出结果中第二行表示船的序号，另：G++ WA了 VC++ AC了

3 2
1 2
2 7
1 3

7
2

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
struct ship
{
    int id,cost;
}ka[100000],ca[100000];
bool cmp(ship a,ship b)
{
    return a.cost>b.cost;
}
int total1[100000],total2[100000];
int n,v,sum[100000],t;
int main()
{
  // freopen("cin.txt","r",stdin);
    //freopen("cout.txt","w",stdout);
    while(~scanf("%d%d",&n,&v))
    {
        int num1=0,num2=0;
        for(int i=1;i<=n;i++) {
            scanf("%d",&t);
            if(t==1) {scanf("%d",&ka[num1].cost);ka[num1++].id=i;}
            else {scanf("%d",&ca[num2].cost);ca[num2++].id=i;}
        }
        sort(ka,ka+num1,cmp);
        //for(int i=0;i<num1;i++) printf("i=%d %d  ",ka[i].id,ka[i].cost);printf("\n");
        sort(ca,ca+num2,cmp);
        //for(int i=0;i<num2;i++) printf("i=%d %d  ",ca[i].id,ca[i].cost);printf("\n");
        int p1=0,p2=0,ans=0;
        total1[0]=0,total2[0]=0,total1[1]=ka[0].cost,total2[1]=ca[0].cost;
        for(int i=1;i<num1;i++) total1[i+1]=total1[i]+ka[i].cost;
        for(int i=1;i<num2;i++) total2[i+1]=total2[i]+ca[i].cost;
        int cnt=0,t,tmp,max0=-1,max1=-1,max2=-1;
        for(int i=0;i<=num2;i++)
        {
            if(i*2>v) break;
            t=v-i*2;
            if(t>num1) t=num1;
            if(total2[i]+total1[t]>max0)
            {
                max0=total2[i]+total1[t];
                max1=t;
                max2=i;
            }
        }
        printf("%d\n",max0);
        for(int i=0;i<max1;i++) printf("%d ",ka[i].id);
        for(int i=0;i<max2;i++) printf("%d ",ca[i].id);
        printf("\n");
    }
    return 0;
}