首页 > 代码库 > 题目1082:代理服务器(贪心算法)
题目1082:代理服务器(贪心算法)
题目链接:http://ac.jobdu.com/problem.php?pid=1082
详解链接:https://github.com/zpfbuaa/JobduInCPlusPlus
参考代码:
//// 1082 代理服务器.cpp// Jobdu//// Created by PengFei_Zheng on 03/05/2017.// Copyright © 2017 PengFei_Zheng. All rights reserved.// #include <stdio.h>#include <iostream>#include <algorithm>#include <string.h>#include <cstring>#include <cmath>#include <climits>#define MAX_SIZE 1001#define MAX_SERVER 5001//#define debugusing namespace std; int n, m; struct Server{//define the struct of server int x, y, z, w; bool operator == (const Server &a) const{//reload the == operator return (x==a.x && y==a.y && z==a.z && w==a.w); }}; Server s1[MAX_SIZE];Server s2[MAX_SERVER]; int main(){#ifdef debug freopen("/Users/pengfei_zheng/Desktop/input.txt", "r", stdin);#endif while(scanf("%d",&n)!=EOF){ for(int i = 0 ; i < n ; i++){ scanf("%d.%d.%d.%d",&s1[i].x,&s1[i].y,&s1[i].z,&s1[i].w); } scanf("%d",&m); for(int i = 0 ; i < m ; i++){ scanf("%d.%d.%d.%d",&s2[i].x,&s2[i].y,&s2[i].z,&s2[i].w); } if(1==n){//special case int i; for(i = 0 ; i < m ; i++){ if(s1[0]==s2[i]){ break; } } if(i<m) printf("-1\n"); else printf("0\n"); } else{ bool loopFlag = true; int start=0, ans = 0, idx = 0; int maxIdx; while(loopFlag){ maxIdx = -1; loopFlag = false; for(int i = 0 ; i < n ; i++){ idx = start; while(idx < m && !(s1[i]==s2[idx])){ idx++; } maxIdx = max(maxIdx,idx);// find the last appear server } if(maxIdx < m){ //judge whether this server can reach all the other servers ans++; loopFlag = true; } start = maxIdx + 1; //update the start Idx } printf("%d\n",ans); } } return 0;}/************************************************************** Problem: 1082 User: zpfbuaa Language: C++ Result: Accepted Time:10 ms Memory:1612 kb****************************************************************/
题目1082:代理服务器(贪心算法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。