codejam一道测试题,希望能得到一些启发

Question

For example, assume these are your initial guesses:code = $20
jam = $15
foo = $40
bar = $30
google = $60
If the correct ordering is code jam foo bar google, then you would need to change two of your prices in order to match the correct ordering. You might change one guess to read jam = $30 and another guess to read bar = $50, which would match the correct ordering and produce the output set bar jam. However, the output set bar code comes before bar jam lexicographically, and you can match the correct ordering by changing your guesses for these items as well.
中文的一些解释吧
输入文件如下(省略了一些)
code jam foo bar google
20 15 40 30 60
第一行的代表物品,第二行的代表价格.现在可以通过调整价格使其按按低到高排序.
所以对于例子可以通过调整bar code的价格使其排序,当然也可以调整bar jam的价格使其排序.(调整价格要最少的次数的,这里必须调整2件东西的价格)
但按字典排序 bar code位于bar jam之前.输出的结果是bar code.希望指点一下,怎么输出结果

Answer 1

此回复为自动发出,仅用于显示而已，并无任何其他特殊作用
楼主【wunaixiwunai】截止到2008-07-10 20:35:08的历史汇总数据(不包括此帖)：
发帖的总数量:5                        发帖的总分数:260                      每贴平均分数:52                       
回帖的总数量:4                        得分贴总数量:1                        回帖的得分率:25%                      
结贴的总数量:3                        结贴的总分数:200                      
无满意结贴数:0                        无满意结贴分:0                        
未结的帖子数:2                        未结的总分数:60                       
结贴的百分比:60.00 %               结分的百分比:76.92 %                  
无满意结贴率:0.00  %               无满意结分率:0.00  %                  
楼主加油

Answer 2

代码 public static void main(String[] args) {
String[] products = {"a", "b", "c", "d", "e", "f", "g"};
int[]    prices   = {10,  20,  5,   7,   30,  32,  60};
int      len      = prices.length;
int      subLen   = 0;
                //最长因子，不在顺序里的为0，如果源数据有负数和0，建议使用Integer，不在的为null
int[]    tmp      = new int[len];  
int      start    = 0;

//找出最长由小到大的因子，subLen因子长度
while(subLen < len - start) {
int[] tmp1 = new int[len];
int tmpSubLen = 1;
int min = prices[start];
tmp1[start] = prices[start];
for(int i = start; i<len-1; i++) {
if(min < prices[i+1]) {
tmpSubLen++;
tmp1[i+1] = prices[i+1];
min = prices[i+1];
}
}
if(tmpSubLen > subLen) {
subLen = tmpSubLen;
tmp = tmp1;
}
start++;
}

for(int i = 1; i < len; i++) {
//根据前后是价格修改不符合要求的价格
if(tmp[i] == 0) {
if(tmp[i+1] != 0) {
if((tmp[i-1]+1) >= tmp[i+1]) tmp[i]=tmp[i+1];
else tmp[i] = tmp[i-1] + 1;
} else tmp[i] = tmp[i-1] + 1;
System.out.println("change "+products[i]+" price:"+prices[i]+" to "+tmp[i]);
}
}

System.out.println("change "+(len - subLen)+" products, new order:");
for(int i = 0; i < len; i++) {
System.out.println(products[i]+":"+tmp[i]+". old price:"+prices[i]);
}
}