安徽区块链虚拟币网站开发价格,网站服务器内网打不开网页,企业推广的网站,展示型网站制作公司题目 某购物城有m个商铺#xff0c;现决定举办一场活动选出人气最高店铺。活动共有n位市民参与#xff0c;每位市民只能投一票#xff0c;但1号店铺如果给该市民发放q元的购物补贴#xff0c;该市民会改为投1号店铺。请计算1号店铺需要最少发放多少元购物补贴才能成为人气最…题目 某购物城有m个商铺现决定举办一场活动选出人气最高店铺。活动共有n位市民参与每位市民只能投一票但1号店铺如果给该市民发放q元的购物补贴该市民会改为投1号店铺。请计算1号店铺需要最少发放多少元购物补贴才能成为人气最高店铺(即获得的票数要大于其他店铺)如果1号店铺本身就是票数最高店铺返回0。 输入描述: 第一行为小写逗号分割的两个整数nm其中第一个整数n表示参与的市民总数第二个整数m代表店铺总数1 n,m 3000. 第2到n1行每行为小写逗号分割的两个整数pq表示市民的意向投票情况其中每行的第一个整数p表示该市民意向投票给p号店铺第二个整数q表示其改投1号店铺所需给予的q元购物补贴1 p m,1q 10^9.不考虑输入的格式问题 输出描述 1号店铺需要最少发放购物补贴金额。 示例1 输入: 5,5 2,10 3,20 4,30 5,40 5,90 输出: 50 说明: 有5个人参与共5个店铺。 如果选择发放10元20元30元60元的补贴来抢2,3,4号店铺的票总共发放了60元补贴(5号店铺有2票1号店铺要3票才能胜出) 如果选择发放10元40元50元的补贴来抢2,5号店铺的票总共发放了50元补贴(抢了5号店铺的票后现在1号店铺只要2票就能胜出) 所以最少发放50元补贴 示例2 输入: 5,5 2,10 3,20 4,30 5,80 5,90 输出: 60说明: 有5个人参与共5个店铺. 如果选择发放10元20元30元60元的补贴来抢2,3,4号店铺的票总共发放了60元补贴(5号店铺有2票1号店铺要3票才能胜出) 如果选择发放10元80元90元的补贴来抢2,5号店铺的票总共发放了90元补贴(抢了5号店铺的票后现在1号店铺只要2票就能胜出) 所以最少发放60元补贴 思路
组合思路列举所有的可能输出满足条件的最少补贴。组合套路详见【JAVA-排列组合】一个套路速解排列组合题 定义votes数组存放每个店铺的意向情况其中votes[0]代表人气最高店铺的索引votes[1]代表1号店铺的的票数量在将输入存入votes时需注意 当某个店铺的人气大于votes[0]店铺的人气即votes[votes[0]]将该店铺的索引存入votes[0] 当某个店铺的人气等于votes[0]店铺的人气且该店铺不是一号店铺时也应该将该店铺的索引存入votes[0]。这样就能保证只有当votes[0]1时1号店铺是唯一的人气最高店铺。对于每行输入转为id和price存入实体VotePrice中并加入到一个list因为是要通过给list中的店铺发放补贴从而将票数给到1号店铺所以list中不存放1号店铺自身的信息。 选择组合时应该考虑剪枝条件比如对以下数据 3,5 3,10 4,25 2,25 2,90 不剪枝时以下两种组合可能对会遍历一次 3,5、4,25、2,25 3,10、4,25、2,25 很明显第二次遍历是冗余情况第一种花5的代价就能拉取到商铺3的投票第二种却要10的代价。所以当组合中只选一个3时选了5的代价就没必要选10。此时应该剪枝。list应该按照id,price升序排序 通过组合可以列举所有可能的情况计算抢了某些店铺的票后当前的votes中的人气最高的唯一店铺是否是1号店铺。比如记当前抢的店铺为cur(list.get(i)) 那么需要更新人气 votes[1]; votes[cur.getId()]–; 回溯移出时则相反 votes[1]–; votes[cur.getId()];最后检查votes中最高人气的唯一店铺(check方法)是否是1号店铺且补贴使用最少即可 因为最后需要输入的是最少补贴即不关心具体有哪些组合所以组合中可以删除中间的path变量 题解
package hwod;import java.util.*;public class VoteMall {public static void main(String[] args) {Scanner sc new Scanner(System.in);String[] firstLines sc.nextLine().split(,);int n Integer.parseInt(firstLines[0]);int m Integer.parseInt(firstLines[1]);int[] votes new int[m 1];ListVotePrice list new ArrayList();for (int i 0; i n; i) {String[] lines sc.nextLine().split(,);int id Integer.parseInt(lines[0]);int price Integer.parseInt(lines[1]);if (id ! 1) list.add(new VotePrice(id, price));votes[id];if (votes[id] votes[votes[0]] || (id ! 1 votes[id] votes[votes[0]])) {votes[0] id;}}System.out.println(voteMall(list, votes));}private static int res Integer.MAX_VALUE;private static int voteMall(ListVotePrice list, int[] votes) {Collections.sort(list);if (votes[0] 1) return 0;//用于剪枝int[] used new int[list.size()];dfs(list, 0, used, votes, 0);return res;}private static void dfs(ListVotePrice list, int start, int[] used, int[] votes, int price) {if (check(Arrays.copyOfRange(votes, 1, votes.length))) {res Math.min(res, price);return;}for (int i start; i list.size(); i) {if (i 0 list.get(i - 1).getId() list.get(i).getId() used[i - 1] 0) continue; //同层相同剪枝VotePrice cur list.get(i);votes[1];votes[cur.getId()]--;used[i] 1;dfs(list, i 1, used, votes, price cur.getPrice());votes[1]--;votes[cur.getId()];used[i] 0;}}private static boolean check(int[] nums) {int maxIdx 0;for (int i 1; i nums.length; i) {if (nums[i] nums[maxIdx]) {maxIdx i;}}return maxIdx 0;}}class VotePrice implements ComparableVotePrice {private int id;private int price;public int getId() {return id;}public void setId(int id) {this.id id;}public int getPrice() {return price;}public void setPrice(int price) {this.price price;}public VotePrice(int id, int price) {this.id id;this.price price;}Overridepublic int compareTo(VotePrice o) {if (this.getId() ! o.getId()) return this.getId() - o.getId();return this.price - o.price;}
}
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
