栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 2926 Hacker in TopCoder

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 2926 Hacker in TopCoder

#include <cstdio>#include <limits>#include <algorithm>#include <functional>int zju[1000];int rate[5000];int range[30][2];int dp[30];inline int rating(int x, int l, int r){    if(x >= l) return x - l + 1;    else if(x <= r) return r - x + 1;    else return 0;}int main(void){    int n, m, cnt;    while(scanf("%d%d", &n, &m) != EOF) {        for (int i = 0; i < n; i++) scanf("%d", &zju[i]);        for (int i = 0; i < m; i++) scanf("%d", &rate[i]);        if(m == 0) { printf("%dn", 0); continue;        }        cnt = (m + 24) / 25;        std::sort(zju, zju + n, std::greater<int>());        std::sort(rate, rate + m, std::greater<int>());        int ans = std::numeric_limits<int>::max() / 2;        for (int i = 0; i <= cnt; i++) { int t = i, c = 0; while(t < m) {       dp[c + 1] = std::numeric_limits<int>::max() / 2;     if(t == 0) range[c][0] = std::numeric_limits<int>::max() / 2;     else range[c][0] = rate[t - 1];     range[c][1] = rate[t];     t += cnt;     ++c; } if(t == m && (m + c + 24) / 25 == cnt && (m + c + 24 + 1) / 25 == cnt + 1) {     range[c][0] = rate[t - 1];     range[c][1] = std::numeric_limits<int>::min() / 2;     ++c; } if(c > n || (m + c + 24) / 25 == cnt) continue; for (int j = 0; j < n; j++)     for (int k = c - 1; k >= 0; k--)         dp[k + 1] = std::min(dp[k + 1], dp[k] + rating(zju[j], range[k][0], range[k][1])); ans = std::min(ans, dp[c]);        }        if(ans == std::numeric_limits<int>::max() / 2) printf("Impossiblen");        else printf("%dn", ans);    }    return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/379551.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号