UVA-12124, Assemble

這題一開始沒想到
以為是要用二為搜索數找最小值
後來才發現直接二分搜下去就好了

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstdlib>

 4 #include <cstring>

 5 #include <set>

 6 #include <map>

 7 #include <vector>

 8 using namespace std;

 9 struct cmp_str{

10     bool operator()(char const *a, char const *b)const{

11         return ( strcmp(a, b)<0 );

12     }

13 };

14 int main(){

15     int T;

16     int n, budget;

17     char junk[21];

18     int qua, cost;

19     map<char const*, int, cmp_str> type;

20     int notype;

21     pair<map<char const*, int, cmp_str>::iterator,bool> tp;

22     vector<map<int, int> > com(1001);

23     pair<map<int, int>::iterator,bool> cp;

24     map<int,int>::reverse_iterator it, cend;

25     int minc, maxq, M, L, R, tmpc;

26     scanf("%d", &T);

27     pair<int,int> MAX(1000000001, 1000001);

28     while(T--){

29         notype=0; maxq=0;

30         type.clear();

31         scanf("%d%d", &n, &budget);

32         for(int i=0 ; i<n ; ++i)

33             com[i].clear();

34 

35         for(int i=0 ; i<n ; ++i){

36             char* ty = new char[21];

37             scanf("%s%s%d%d", ty, junk, &cost, &qua);

38             if(maxq < qua) maxq=qua;

39             tp=type.insert(pair<char const*, int>(ty, notype));

40             if(tp.second){

41                 ++notype;

42             }

43             cp=com[tp.first->second].insert(pair<int,int>(qua, cost));

44             if(not cp.second){

45                 if(cp.first->second > cost)

46                     cp.first->second=cost;

47             }

48         }

49         for(int i=0 ; i<notype ; ++i){

50             cend=com[i].rend(); it=com[i].rbegin();

51             minc=it->second; it++;

52             for( ; it!=cend ; it++){

53                 if(it->second > minc){

54                     it->second = minc;

55                 }else{

56                     minc=it->second;

57                 }

58             }

59             com[i].insert(com[i].end() , MAX);

60         }

61         L=0, R=maxq+1;

62         while(R-L!=1){

63             M=(L+R)/2;

64             tmpc=0;

65             for(int i=0 ; i<notype ; ++i){

66                 tmpc+=com[i].lower_bound(M)->second;

67                 if(com[i].lower_bound(M)->first == 1000000001){ //no match

68                     tmpc=budget+1;

69                     break;

70                 }

71             }

72             if(tmpc > budget){

73                 R=M;

74             }else{

75                 L=M;

76             }

77         }

78         printf("%d\n", L);

79     }

80     return 0;

81 }