URAL 2092 Bolero 贪心

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
typedef  long long  ll;

#define MM(a,b) memset(a,b,sizeof(a));
#define inf 0x7f7f7f7f
#define FOR(i,n) for(int i=1;i<=n;i++)
#define CT continue;
#define PF printf
#define SC scanf
const int maxn=100000+10;

struct node{
   ll val;int id;
   bool operator<(const node &a) const{
      return this->val>a.val;
   }
};
vector<int> G[105];
priority_queue<node> q;
int num[105],g[105];
int main()
{
    int n,m;
    while(~SC("%d%d",&n,&m)){
        ll ori=0,ans=0;
        for(int i=0;i<=100;i++) G[i].clear();
        FOR(i,n) {
            int cost,p;
            SC("%d%d",&cost,&p);
            ori+=cost*(100-p);
            G[p].push_back(cost);
        }
       for(int i=0;i<=100;i++) sort(G[i].begin(),G[i].end());
        MM(num,inf);
        FOR(i,m){
           int peo,dis;
           SC("%d%d",&peo,&dis);
           num[dis]=min(num[dis],peo);
        }
       // PF("111111\n");
        ans=ori;
        FOR(k,100){
           if(num[k]>n) CT;
           MM(g,0);
         //  PF("2222222\n");
           ll tmp=ori,cnt=0;
           for(int i=0;i<=k;i++)
           for(int j=0;j<G[i].size();j++){
                tmp+=G[i][j]*(i-k);cnt++;
              }
         //  PF("3333333\n");
           while(q.size()) q.pop();
           for(int i=k+1;i<=100;i++) {
               if(G[i].size()) q.push((node){G[i][0]*(i-k),i});
               g[i]=1;
           }
         //  PF("444444\n");
           while(cnt<num[k]){
              node u=q.top();q.pop();
              tmp+=u.val;
              cnt++;
              if(g[u.id]<G[u.id].size()){
                  int r=g[u.id];
                  q.push((node){G[u.id][r]*(u.id-k),u.id});
                  g[u.id]++;
              }
           }
           ans=min(ans,tmp);
        }
        PF("%.2f\n",(double)ans/100.00);
    }
    return 0;
}