3月16号 借这TopCoder和共同举办的软件编程(算法)竞赛，第一次在topcoder Competition Arena竞赛，由于是全英文，前几天熟悉了下界面。下面给出 500分的题目.
Problem Statement
????
Customers are standing in the checkout line at the market, waiting for cashiers to become available. When a cashier is available, the first customer in line starts getting served. If more than one cashier is available, the customer goes to the first of them. After having all their items processed, the customer pays and exits the market (we consider this to happen instantly).
Customers buy different amounts of groceries and cashiers work at different paces. Because of this, a customer may exit the market later than someone who was behind them in line.
You will be given two vector <int>s, customerItems and timePerItem. Each element of customerItems is the number of items a customer has in his cart. The customers will be given in the order in which they are standing in line. Each element of timePerItem corresponds to one cashier and represents the number of seconds needed for that cashier to process one grocery item.
Return the number of customers that exit the market strictly later than someone who was behind them in line.
Definition
????
Class:
MarketQueue
Method:
anomalies
Parameters:
vector <int>, vector <int>
Returns:int
Method signature:
int anomalies(vector <int> customerItems, vector <int> timePerItem)
(be sure your method is public)
????
Constraints
-
customerItems will contain between 1 and 50 elements, inclusive.
-
Each element of customerItems will be between 1 and 100, inclusive.
-
timePerItem will contain between 1 and 10 elements, inclusive.
-
Each element of timePerItem will be between 1 and 100, inclusive.
Examples
0)
????
{ 3, 4 }
{ 5, 5 }
Returns: 0
Both customers get served immediately. Customer 0 goes to the first cashier who needs 5 seconds to process each of the customer's 3 items, so the customer exits after 15 seconds. Customer 1 goes to the second cashier and exits after 4*5 = 20 seconds.
1)
????
{ 3, 4 }
{ 10, 7 }
Returns: 1
This time customer 1 finishes after 28 seconds, before customer 0 who finishes after 30 seconds.
2)
????
{ 3, 3, 15, 1 }
{ 5, 5, 2 }
Returns: 1
Customer 3 gets done before customer 2.
3)
????
{ 89, 28, 13, 94, 82, 1, 88, 88, 16, 7, 83 }
{ 25, 96, 90, 96, 10 }
Returns: 5
Customers 0, 1, 2, 3 and 7 exit later than someone who was behind them in line.
题目大概意思是说：客户们进入超市，组成队列，超市会给客户发个卡，卡上记录该客户前面要等待多少人。客户买完东西去结帐，如果有收银员空闲，最开始进来的客户去结帐，有两个收银员空闲，前面两个进来的客户去结帐，以此类推。要求计算有多少个客户比排在他后面的客户晚去结帐出超市。(最好结合给出的例子，理解题目意思)
比如上面给出例子（2）
{ 3, 3, 15, 1 }
{ 5, 5, 2 }
Returns: 1
Customer 3 gets done before customer 2.
第0个客户15s,第一个15s,第二个30,第三个20s, 第二个比第三个晚，其他没有比自己后面晚的，返回1
给出我做的(比赛时没做完，看题目都看了满久):
#include <iostream>
#include <string>
#include <stdio.h>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;
class MarketQueue
{
public:
int times[10];
int customers[50];
int anomalies(vector <int> customerItems, vector <int> timePerItem)
{ int len_customerItems,len_timePerItem,pos,min,num;
if (check_Items(customerItems,timePerItem)==false) return-1 ;
len_customerItems = customerItems.size();
len_timePerItem = timePerItem.size();
memset(times,0,sizeof(times));
for(int i=0 ; i<len_customerItems;i++)
{
pos = -1;
min=times[0];
for(int j =1;j<len_timePerItem ;j++)
{
if(times[j]<min) { pos = j; min = times[j] }
}
times[pos]+= customerItems[i]*timePerItem[pos];
customers[i] = times[pos];
}
num = 0
for(int i=0 ; i<len_customerItems;i++)
{
for(int j =i;j<len_customerItems;j++)
if (customers[i]<customers[j]) num++;
}
return num;
}
bool check_Items(vector <int> customerItems, vector <int> timePerItem)//检测 数据是否合法
{
if (customerItems.size()>50) return false;
for(int i =0 ; i<customerItems.size ; i++)
{
if (customerItems[i]>100) return false;
}
if (timePerItem.size()>10) return false;
for(int i =0 ; i<customerItems.size ; i++)
{
if (customerItems[i]>100) return false;
}
return true;
}
};
其实题目并不难，写完后 提交，几分钟后是挑战阶段，如果别人看出你的问题，提交数据导致你的程序出错，他的得分，你扣分，是不是很有意思。看看别人的代码可以学习学习，里面高手满多的。
